EditDistanceTable.cpp 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628
  1. /* EditDistanceTable.c
  2. *
  3. * Copyright (C) 2012, 2014-2017 David Weenink
  4. *
  5. * This code is free software; you can redistribute it and/or modify
  6. * it under the terms of the GNU General Public License as published by
  7. * the Free Software Foundation; either version 2 of the License, or (at
  8. * your option) any later version.
  9. *
  10. * This code is distributed in the hope that it will be useful, but
  11. * WITHOUT ANY WARRANTY; without even the implied warranty of
  12. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  13. * General Public License for more details.
  14. *
  15. * You should have received a copy of the GNU General Public License
  16. * along with this work. If not, see <http://www.gnu.org/licenses/>.
  17. */
  18. /*
  19. djmw 20120407 First implementation
  20. */
  21. #include "EditDistanceTable.h"
  22. #include "oo_DESTROY.h"
  23. #include "EditDistanceTable_def.h"
  24. #include "oo_COPY.h"
  25. #include "EditDistanceTable_def.h"
  26. #include "oo_EQUAL.h"
  27. #include "EditDistanceTable_def.h"
  28. #include "oo_CAN_WRITE_AS_ENCODING.h"
  29. #include "EditDistanceTable_def.h"
  30. #include "oo_WRITE_TEXT.h"
  31. #include "EditDistanceTable_def.h"
  32. #include "oo_WRITE_BINARY.h"
  33. #include "EditDistanceTable_def.h"
  34. #include "oo_READ_TEXT.h"
  35. #include "EditDistanceTable_def.h"
  36. #include "oo_READ_BINARY.h"
  37. #include "EditDistanceTable_def.h"
  38. #include "oo_DESCRIPTION.h"
  39. #include "EditDistanceTable_def.h"
  40. // prototypes
  41. autoEditCostsTable EditCostsTable_createDefault ();
  42. /* The insertion, deletion and substitution costs are specified in a TableOfReal
  43. * 1..n-2 target symbols/alphabet
  44. * 1..m-2 source symbols/alphabet
  45. * row n-1 and col m-1 specify nomatch symbols
  46. * cells [n] [1..m-2] specify insertion costs
  47. * cells [1..n-1] [m] specify deletion costs
  48. * cell [n-1] [m-1] if nomatch target == nomatch source
  49. * cell [n] [m] if nomatch target != nomatch source
  50. */
  51. Thing_implement (WarpingPath, Daata, 0);
  52. autoWarpingPath WarpingPath_create (integer length) {
  53. try {
  54. autoWarpingPath me = Thing_new (WarpingPath);
  55. my path = NUMvector<structPairOfInteger> (1, length);
  56. my _capacity = my pathLength = length;
  57. return me;
  58. } catch (MelderError) {
  59. Melder_throw (U"WarpPath not created.");
  60. }
  61. }
  62. static void WarpingPath_reset (WarpingPath me) {
  63. for (integer i = 1; i <= my _capacity; i ++) {
  64. my path [i].x = my path [i].y = 0;
  65. }
  66. my pathLength = my _capacity;
  67. }
  68. static void WarpingPath_getPath (WarpingPath me, short **psi, integer iy, integer ix) { // psi [0..nrows-1] [0..ncols-1]
  69. integer index = my pathLength;
  70. my path [index].x = ix;
  71. my path [index].y = iy;
  72. while (!(ix == 0 && iy == 0)) {
  73. if (psi [iy] [ix] == WARPING_fromLeft) {
  74. ix --;
  75. } else if (psi [iy] [ix] == WARPING_fromBelow) {
  76. iy --;
  77. } else { // WARPING_fromDiag
  78. ix --; iy --;
  79. }
  80. my path [-- index].x = ix;
  81. my path [index].y = iy;
  82. }
  83. if (index > 1) {
  84. integer k = 1;
  85. for (integer i = index; i <= my pathLength; i ++) {
  86. my path [k ++] = my path [i];
  87. my path [i].x = my path [i].y = 0;
  88. }
  89. my pathLength = k - 1;
  90. }
  91. }
  92. static void WarpingPath_shiftPathByOne (WarpingPath me) {
  93. for (integer i = 1; i <= my pathLength; i ++) {
  94. (my path [i].x) ++; (my path [i].y) ++;
  95. }
  96. }
  97. integer WarpingPath_getColumnsFromRowIndex (WarpingPath me, integer iy, integer *p_ix1, integer *p_ix2) {
  98. integer ix1 = 0, ix2 = 0, numberOfColumns = 0;
  99. if (iy > 0) {
  100. for (integer i = 1; i <= my pathLength; i ++) {
  101. if (my path [i].y < iy) {
  102. continue;
  103. } else if (my path [i].y == iy) {
  104. if (ix1 == 0) {
  105. ix1 = my path [i].x;
  106. }
  107. ix2 = my path [i].x;
  108. } else {
  109. break;
  110. }
  111. }
  112. numberOfColumns = ix2 - ix1 + 1;
  113. }
  114. if (p_ix1) {
  115. *p_ix1 = ix1;
  116. }
  117. if (p_ix2) {
  118. *p_ix2 = ix2;
  119. }
  120. return numberOfColumns;
  121. }
  122. integer WarpingPath_getRowsFromColumnIndex (WarpingPath me, integer ix, integer *p_iy1, integer *p_iy2) {
  123. if (ix <= 0) {
  124. return 0;
  125. }
  126. integer iy1 = 0, iy2 = 0, numberOfRows = 0;
  127. if (ix > 0) {
  128. for (integer i = 1; i <= my pathLength; i ++) {
  129. if (my path [i].x < ix) {
  130. continue;
  131. } else if (my path [i].x == ix) {
  132. if (iy1 == 0) {
  133. iy1 = my path [i].y;
  134. }
  135. iy2 = my path [i].y;
  136. } else {
  137. break;
  138. }
  139. }
  140. numberOfRows = iy2 - iy1 + 1;
  141. }
  142. if (p_iy1) {
  143. *p_iy1 = iy1;
  144. }
  145. if (p_iy2) {
  146. *p_iy2 = iy2;
  147. }
  148. return numberOfRows;
  149. }
  150. Thing_implement (EditCostsTable, TableOfReal, 0);
  151. void structEditCostsTable :: v_info () {
  152. EditDistanceTable_Parent :: v_info ();
  153. MelderInfo_writeLine (U"Target:", numberOfRows - 2, U" symbols.");
  154. MelderInfo_writeLine (U"Source:", numberOfColumns - 2, U" symbols.");
  155. }
  156. bool structEditCostsTable :: v_matchTargetSymbol (conststring32 targetSymbol, conststring32 symbol) {
  157. return Melder_equ (targetSymbol, symbol);
  158. }
  159. bool structEditCostsTable :: v_matchSourceSymbol (conststring32 sourceSymbol, conststring32 symbol) {
  160. return Melder_equ (sourceSymbol, symbol);
  161. }
  162. bool structEditCostsTable :: v_matchTargetWithSourceSymbol (conststring32 targetSymbol, conststring32 sourceSymbol) {
  163. return Melder_equ (targetSymbol, sourceSymbol);
  164. }
  165. autoEditCostsTable EditCostsTable_create (integer targetAlphabetSize, integer sourceAlphabetSize) {
  166. try{
  167. autoEditCostsTable me = Thing_new (EditCostsTable);
  168. TableOfReal_init (me.get(), targetAlphabetSize + 2, sourceAlphabetSize + 2);
  169. return me;
  170. } catch (MelderError) {
  171. Melder_throw (U"EditCostsTable not created.");
  172. }
  173. }
  174. autoEditCostsTable EditCostsTable_createDefault () {
  175. try {
  176. autoEditCostsTable me = EditCostsTable_create (0, 0);
  177. my data [1] [1] = 0; // default substitution cost (nomatch == nomatch)
  178. my data [2] [2] = 2; // default substitution cost (nomatch != nomatch)
  179. my data [2] [1] = 1; // default insertion cost
  180. my data [1] [2] = 1; // default deletion cost
  181. return me;
  182. } catch (MelderError) {
  183. Melder_throw (U"Default EditCostsTable not created.");
  184. }
  185. }
  186. void EditCostsTable_setDefaultCosts (EditCostsTable me, double insertionCosts, double deletionCosts, double substitutionCosts) {
  187. my data [my numberOfRows - 1] [my numberOfColumns - 1] = 0;
  188. my data [my numberOfRows] [my numberOfColumns] = substitutionCosts;
  189. my data [my numberOfRows] [my numberOfColumns - 1] = deletionCosts;
  190. my data [my numberOfRows - 1] [my numberOfColumns] = insertionCosts;
  191. }
  192. integer EditCostsTable_getTargetIndex (EditCostsTable me, conststring32 symbol) {
  193. for (integer i = 1; i <= my numberOfRows - 2; i ++) {
  194. if (my v_matchTargetSymbol (my rowLabels [i].get(), symbol)) {
  195. return i;
  196. }
  197. }
  198. return 0;
  199. }
  200. integer EditCostsTable_getSourceIndex (EditCostsTable me, conststring32 symbol) {
  201. for (integer j = 1; j <= my numberOfColumns - 2; j ++) {
  202. if (my v_matchSourceSymbol (my columnLabels [j].get(), symbol)) {
  203. return j;
  204. }
  205. }
  206. return 0;
  207. }
  208. void EditCostsTable_setInsertionCosts (EditCostsTable me, conststring32 targets_string, double cost) {
  209. autostring32vector targets = STRVECtokenize (targets_string);
  210. for (integer itarget = 1; itarget <= targets.size; itarget ++) {
  211. integer irow = EditCostsTable_getTargetIndex (me, targets [itarget].get());
  212. irow = irow > 0 ? irow : my numberOfRows - 1; // nomatch condition to penultimate row
  213. my data [irow] [my numberOfColumns] = cost;
  214. }
  215. }
  216. void EditCostsTable_setDeletionCosts (EditCostsTable me, conststring32 sources_string, double cost) {
  217. autostring32vector sources = STRVECtokenize (sources_string);
  218. for (integer isource = 1; isource <= sources.size; isource ++) {
  219. integer icol = EditCostsTable_getSourceIndex (me, sources [isource].get());
  220. icol = icol > 0 ? icol : my numberOfColumns - 1; // nomatch condition to penultimate column
  221. my data [my numberOfRows] [icol] = cost;
  222. }
  223. }
  224. void EditCostsTable_setOthersCosts (EditCostsTable me, double insertionCost, double deletionCost, double substitutionCost_equal, double substitutionCost_unequal) {
  225. my data [my numberOfRows - 1] [my numberOfColumns] = insertionCost;
  226. my data [my numberOfRows] [my numberOfColumns - 1] = deletionCost;
  227. my data [my numberOfRows - 1] [my numberOfColumns - 1] = substitutionCost_unequal;
  228. my data [my numberOfRows] [my numberOfColumns] = substitutionCost_equal;
  229. }
  230. double EditCostsTable_getOthersCost (EditCostsTable me, int costType) {
  231. return costType == 1 ? my data [my numberOfRows - 1] [my numberOfColumns] : //insertion
  232. costType == 2 ? my data [my numberOfRows] [my numberOfColumns - 1] : // deletion
  233. costType == 3 ? my data [my numberOfRows] [my numberOfColumns] : // equality
  234. my data [my numberOfRows - 1] [my numberOfColumns -1]; // inequality
  235. }
  236. void EditCostsTable_setSubstitutionCosts (EditCostsTable me, conststring32 targets_string, conststring32 sources_string, double cost) {
  237. try {
  238. autostring32vector targets = STRVECtokenize (targets_string);
  239. autostring32vector sources = STRVECtokenize (sources_string);
  240. autoNUMvector<integer> targetIndex (1, my numberOfRows);
  241. autoNUMvector<integer> sourceIndex (1, my numberOfRows);
  242. integer numberOfTargetSymbols = 0;
  243. for (integer itarget = 1; itarget <= targets.size; itarget ++) {
  244. integer index = EditCostsTable_getTargetIndex (me, targets [itarget].get());
  245. if (index > 0) {
  246. targetIndex [ ++numberOfTargetSymbols] = index;
  247. }
  248. }
  249. if (numberOfTargetSymbols == 0) {
  250. targetIndex [ ++numberOfTargetSymbols] = my numberOfRows - 1;
  251. }
  252. integer numberOfSourceSymbols = 0;
  253. for (integer isource = 1; isource <= sources.size; isource ++) {
  254. integer index = EditCostsTable_getSourceIndex (me, sources [isource].get());
  255. if (index > 0) {
  256. sourceIndex [ ++numberOfSourceSymbols] = index;
  257. }
  258. }
  259. if (numberOfSourceSymbols == 0) {
  260. sourceIndex [ ++numberOfSourceSymbols] = my numberOfColumns - 1;
  261. }
  262. for (integer i = 1; i <= numberOfTargetSymbols; i ++) {
  263. integer irow = targetIndex [i];
  264. for (integer j = 1; j <= numberOfSourceSymbols; j ++) {
  265. my data [irow] [sourceIndex [j]] = cost;
  266. }
  267. }
  268. } catch (MelderError) {
  269. Melder_throw (me, U": substitution costs not set.");
  270. }
  271. }
  272. double EditCostsTable_getInsertionCost (EditCostsTable me, conststring32 symbol) {
  273. integer irow = EditCostsTable_getTargetIndex (me, symbol);
  274. irow = irow == 0 ? my numberOfRows - 1 : irow; // others is penultimate row
  275. return my data [irow] [my numberOfColumns];
  276. }
  277. double EditCostsTable_getDeletionCost (EditCostsTable me, conststring32 sourceSymbol) {
  278. integer icol = EditCostsTable_getSourceIndex (me, sourceSymbol);
  279. icol = icol == 0 ? my numberOfColumns - 1 : icol; // others is penultimate column
  280. return my data [my numberOfRows] [icol];
  281. }
  282. double EditCostsTable_getSubstitutionCost (EditCostsTable me, conststring32 symbol, conststring32 replacement) {
  283. integer irow = EditCostsTable_getTargetIndex (me, symbol);
  284. integer icol = EditCostsTable_getSourceIndex (me, replacement);
  285. if (irow == 0 && icol == 0) { // nomatch
  286. irow = my numberOfRows;
  287. icol = my numberOfColumns;
  288. if (my v_matchTargetWithSourceSymbol (symbol, replacement)) {
  289. -- irow;
  290. -- icol;
  291. }
  292. } else {
  293. irow = irow == 0 ? my numberOfRows - 1 : irow;
  294. icol = icol == 0 ? my numberOfColumns - 1 : icol;
  295. }
  296. return my data [irow] [icol];
  297. }
  298. autoTableOfReal EditCostsTable_to_TableOfReal (EditCostsTable me) {
  299. try {
  300. autoTableOfReal thee = TableOfReal_create (my numberOfRows, my numberOfColumns);
  301. for (integer j = 1; j <= my numberOfColumns; j ++)
  302. thy columnLabels [j] = Melder_dup (my columnLabels [j].get());
  303. for (integer i = 1; i <= my numberOfRows; i ++)
  304. thy rowLabels [i] = Melder_dup (my rowLabels [i].get());
  305. matrixcopy_preallocated (thy data.get(), my data.get());
  306. return thee;
  307. } catch (MelderError) {
  308. Melder_throw (me, U": not converted to TableOfReal.");
  309. }
  310. }
  311. Thing_implement (EditDistanceTable, TableOfReal, 0);
  312. void structEditDistanceTable :: v_info () {
  313. EditDistanceTable_Parent :: v_info ();
  314. MelderInfo_writeLine (U"Target:", numberOfRows, U" symbols.");
  315. MelderInfo_writeLine (U"Source:", numberOfColumns, U" symbols.");
  316. }
  317. autoEditDistanceTable EditDistanceTable_create (Strings target, Strings source) {
  318. try {
  319. autoEditDistanceTable me = Thing_new (EditDistanceTable);
  320. integer numberOfSourceSymbols = source -> numberOfStrings, numberOfTargetSymbols = target -> numberOfStrings;
  321. TableOfReal_init (me.get(), numberOfTargetSymbols + 1, numberOfSourceSymbols + 1);
  322. TableOfReal_setColumnLabel (me.get(), 1, U"");
  323. for (integer j = 1; j <= numberOfSourceSymbols; j ++) {
  324. my columnLabels [j + 1] = Melder_dup (source -> strings [j].get());
  325. }
  326. TableOfReal_setRowLabel (me.get(), 1, U"");
  327. for (integer i = 1; i <= numberOfTargetSymbols; i ++) {
  328. my rowLabels [i + 1] = Melder_dup (target -> strings [i].get());
  329. }
  330. my warpingPath = WarpingPath_create (numberOfTargetSymbols + numberOfSourceSymbols + 1);
  331. my editCostsTable = EditCostsTable_createDefault ();
  332. EditDistanceTable_findPath (me.get(), 0);
  333. return me;
  334. } catch (MelderError) {
  335. Melder_throw (U"EditDistanceTable not created.");
  336. }
  337. }
  338. void EditDistanceTable_setEditCosts (EditDistanceTable me, EditCostsTable thee) {
  339. try {
  340. my editCostsTable = Data_copy (thee);
  341. } catch (MelderError) {
  342. Melder_throw (me, U": edit costs not set.");
  343. }
  344. }
  345. autoEditDistanceTable EditDistanceTable_createFromCharacterStrings (const char32 chars1 [], const char32 chars2 []) {
  346. try {
  347. autoStrings s1 = Strings_createAsCharacters (chars1);
  348. autoStrings s2 = Strings_createAsCharacters (chars2);
  349. autoEditDistanceTable me = EditDistanceTable_create (s1.get(), s2.get());
  350. return me;
  351. } catch (MelderError) {
  352. Melder_throw (U"EditDistanceTable not created from character strings.");
  353. }
  354. }
  355. static void NUMrationalize (double x, integer *numerator, integer *denominator) {
  356. double epsilon = 1e-6;
  357. *numerator = 1;
  358. for (*denominator = 1; *denominator <= 100000; (*denominator) ++) {
  359. double numerator_d = x * *denominator, rounded = round (numerator_d);
  360. if (fabs (rounded - numerator_d) < epsilon) {
  361. *numerator = (integer) rounded;
  362. return;
  363. }
  364. }
  365. *denominator = 0; /* Failure. */
  366. }
  367. static void fixRows (TableOfReal me, integer *rowmin, integer *rowmax) {
  368. if (*rowmax < *rowmin) {
  369. *rowmin = 1;
  370. *rowmax = my numberOfRows;
  371. } else if (*rowmin < 1) {
  372. *rowmin = 1;
  373. } else if (*rowmax > my numberOfRows) {
  374. *rowmax = my numberOfRows;
  375. }
  376. }
  377. static void print4 (char *buffer, double value, int iformat, int width, int precision) {
  378. char formatString [40];
  379. if (iformat == 4) {
  380. integer numerator, denominator;
  381. NUMrationalize (value, & numerator, & denominator);
  382. if (numerator == 0)
  383. snprintf (buffer, 40, "0");
  384. else if (denominator > 1)
  385. snprintf (buffer, 40, "%s/%s", Melder8_integer (numerator), Melder8_integer (denominator));
  386. else
  387. snprintf (buffer, 40, "%.7g", value);
  388. } else {
  389. snprintf (formatString, 40, "%%%d.%d%c", width, precision, iformat == 1 ? 'f' : iformat == 2 ? 'e' : 'g');
  390. snprintf (buffer, 40, formatString, value);
  391. }
  392. }
  393. static double getMaxRowLabelWidth (TableOfReal me, Graphics graphics, integer rowmin, integer rowmax) {
  394. double maxWidth = 0.0;
  395. if (! my rowLabels) return 0.0;
  396. fixRows (me, & rowmin, & rowmax);
  397. for (integer irow = rowmin; irow <= rowmax; irow ++) {
  398. if (my rowLabels [irow] && my rowLabels [irow] [0]) {
  399. double textWidth = Graphics_textWidth_ps (graphics, my rowLabels [irow].get(), true); /* SILIPA is bigger than XIPA */
  400. if (textWidth > maxWidth) {
  401. maxWidth = textWidth;
  402. }
  403. }
  404. }
  405. return maxWidth;
  406. }
  407. static double getLeftMargin (Graphics graphics) {
  408. return Graphics_dxMMtoWC (graphics, 1);
  409. }
  410. static double getLineSpacing (Graphics graphics) {
  411. return Graphics_dyMMtoWC (graphics, 1.5 * Graphics_inqFontSize (graphics) * 25.4 / 72);
  412. }
  413. void EditDistanceTable_draw (EditDistanceTable me, Graphics graphics, int iformat, int precision, double angle) {
  414. integer rowmin = 1, rowmax = my numberOfRows;
  415. Graphics_setInner (graphics);
  416. Graphics_setWindow (graphics, 0.5, my numberOfColumns + 0.5, 0, 1);
  417. double leftMargin = getLeftMargin (graphics); // not earlier!
  418. double lineSpacing = getLineSpacing (graphics); // not earlier!
  419. double maxTextWidth = getMaxRowLabelWidth (me, graphics, rowmin, rowmax);
  420. double y = 1 + 0.1 * lineSpacing;
  421. autoNUMmatrix<bool> onPath (1, my numberOfRows, 1, my numberOfColumns);
  422. for (integer i = 1; i <= my warpingPath -> pathLength; i ++) {
  423. structPairOfInteger poi = my warpingPath -> path [i];
  424. onPath [poi.y] [poi.x] = true;
  425. }
  426. for (integer irow = my numberOfRows; irow > 0; irow --) {
  427. Graphics_setTextAlignment (graphics, Graphics_RIGHT, Graphics_HALF);
  428. if (my rowLabels && my rowLabels [irow] && my rowLabels [irow] [0])
  429. Graphics_text (graphics, 0.5 - leftMargin, y, my rowLabels [irow].get());
  430. Graphics_setTextAlignment (graphics, Graphics_CENTRE, Graphics_HALF);
  431. for (integer icol = 1; icol <= my numberOfColumns; icol ++) {
  432. char text [40];
  433. print4 (text, my data [irow] [icol], iformat, 0, precision);
  434. Graphics_setBold (graphics, onPath [irow] [icol]);
  435. Graphics_text (graphics, icol, y, Melder_peek8to32 (text));
  436. if (onPath [irow] [icol]) {
  437. Graphics_rectangle (graphics, icol-0.5, icol+0.5, y - 0.5*lineSpacing, y + 0.5*lineSpacing);
  438. }
  439. }
  440. y -= lineSpacing;
  441. Graphics_setBold (graphics, false);
  442. }
  443. double left = 0.5;
  444. if (maxTextWidth > 0.0) left -= maxTextWidth + 2 * leftMargin;
  445. Graphics_line (graphics, left, y, my numberOfColumns + 0.5, y);
  446. Graphics_setTextRotation (graphics, angle);
  447. if (angle < 0) {
  448. y -= 0.3*lineSpacing;
  449. Graphics_setTextAlignment (graphics, Graphics_LEFT, Graphics_HALF);
  450. } else if (angle > 0) {
  451. Graphics_setTextAlignment (graphics, Graphics_RIGHT, Graphics_HALF);
  452. y -= 0.3*lineSpacing;
  453. } else {
  454. Graphics_setTextAlignment (graphics, Graphics_CENTRE, Graphics_TOP);
  455. }
  456. for (integer icol = 1; icol <= my numberOfColumns; icol ++) {
  457. if (my columnLabels && my columnLabels [icol] && my columnLabels [icol] [0])
  458. Graphics_text (graphics, icol, y, my columnLabels [icol].get());
  459. }
  460. Graphics_setTextRotation (graphics, 0);
  461. y -= lineSpacing;
  462. Graphics_line (graphics, 0.5, y, 0.5, 1 + 0.5 * lineSpacing);
  463. Graphics_unsetInner (graphics);
  464. }
  465. void EditDistanceTable_drawEditOperations (EditDistanceTable me, Graphics graphics) {
  466. conststring32 oinsertion = U"i", insertion = U"*", odeletion = U"d", deletion = U"*", osubstitution = U"s", oequal = U"";
  467. Graphics_setWindow (graphics, 0.5, my warpingPath -> pathLength - 0.5, 0, 1); // pathLength-1 symbols
  468. double lineSpacing = getLineSpacing (graphics);
  469. double ytarget = 1 - lineSpacing, ysource = ytarget - 2 * lineSpacing, yoper = ysource - lineSpacing;
  470. Graphics_setTextAlignment (graphics, Graphics_CENTRE, Graphics_BOTTOM);
  471. for (integer i = 2; i <= my warpingPath -> pathLength; i ++) {
  472. structPairOfInteger p = my warpingPath -> path [i], p1 = my warpingPath -> path [i - 1];
  473. double x = i - 1;
  474. if (p.x == p1.x) { // insertion
  475. Graphics_text (graphics, x, ytarget, my rowLabels [p.y].get());
  476. Graphics_text (graphics, x, ysource, deletion);
  477. Graphics_text (graphics, x, yoper, oinsertion);
  478. } else if (p.y == p1.y) { // deletion
  479. Graphics_text (graphics, x, ytarget, insertion);
  480. Graphics_text (graphics, x, ysource, my columnLabels [p.x].get());
  481. Graphics_text (graphics, x, yoper, odeletion);
  482. } else { // substitution ?
  483. Graphics_text (graphics, x, ytarget, my rowLabels [p.y].get());
  484. Graphics_text (graphics, x, ysource, my columnLabels [p.x].get());
  485. Graphics_text (graphics, x, yoper, (Melder_equ (my rowLabels [p.y].get(), my columnLabels [p.x].get()) ? oequal : osubstitution));
  486. }
  487. Graphics_line (graphics, x, ysource + lineSpacing, x, ytarget - 0.1 * lineSpacing);
  488. }
  489. }
  490. void EditDistanceTable_setDefaultCosts (EditDistanceTable me, double insertionCosts, double deletionCosts, double substitutionCosts) {
  491. EditCostsTable_setDefaultCosts (my editCostsTable.get(), insertionCosts, deletionCosts, substitutionCosts);
  492. EditDistanceTable_findPath (me, 0);
  493. }
  494. autoTableOfReal EditDistanceTable_to_TableOfReal_directions (EditDistanceTable me) {
  495. autoTableOfReal tor;
  496. EditDistanceTable_findPath (me, & tor);
  497. return tor;
  498. }
  499. void EditDistanceTable_findPath (EditDistanceTable me, autoTableOfReal *out_directions) {
  500. try {
  501. /* What do we have to do to source to get target?
  502. * Origin [0] [0] is at bottom-left corner
  503. * Target vertical, source horizontal
  504. * Going in the vertical direction is a deletion, horizontal is insertion, diagonal is substitution
  505. */
  506. integer numberOfSources = my numberOfColumns - 1, numberOfTargets = my numberOfRows - 1;
  507. autoNUMmatrix<short> psi (0, numberOfTargets, 0, numberOfSources);
  508. autoNUMmatrix<double> delta (0, numberOfTargets, 0, numberOfSources);
  509. for (integer j = 1; j <= numberOfSources; j ++) {
  510. delta [0] [j] = delta [0] [j - 1] + EditCostsTable_getDeletionCost (my editCostsTable.get(), my columnLabels [j+1].get());
  511. psi [0] [j] = WARPING_fromLeft;
  512. }
  513. for (integer i = 1; i <= numberOfTargets; i ++) {
  514. delta [i] [0] = delta [i - 1] [0] + EditCostsTable_getInsertionCost (my editCostsTable.get(), my rowLabels [i+1].get());
  515. psi [i] [0] = WARPING_fromBelow;
  516. }
  517. for (integer j = 1; j <= numberOfSources; j ++) {
  518. for (integer i = 1; i <= numberOfTargets; i ++) {
  519. // the substitution, deletion and insertion costs.
  520. double left = delta [i] [j - 1] + EditCostsTable_getInsertionCost (my editCostsTable.get(), my rowLabels [i+1].get());
  521. double bottom = delta [i - 1] [j] + EditCostsTable_getDeletionCost (my editCostsTable.get(), my columnLabels [j+1].get());
  522. double mindist = delta [i - 1] [j - 1] +
  523. EditCostsTable_getSubstitutionCost (my editCostsTable.get(), my rowLabels [i+1].get(), my columnLabels [j+1].get()); // diag
  524. psi [i] [j] = WARPING_fromDiag;
  525. if (bottom < mindist) {
  526. mindist = bottom;
  527. psi [i] [j] = WARPING_fromBelow;
  528. }
  529. if (left < mindist) {
  530. mindist = left;
  531. psi [i] [j] = WARPING_fromLeft;
  532. }
  533. delta [i] [j] = mindist;
  534. }
  535. }
  536. // find minimum distance in last column
  537. integer iy = numberOfTargets, ix = numberOfSources;
  538. WarpingPath_reset (my warpingPath.get());
  539. WarpingPath_getPath (my warpingPath.get(), psi.peek(), iy, ix);
  540. WarpingPath_shiftPathByOne (my warpingPath.get());
  541. for (integer i = 0; i <= numberOfTargets; i ++) {
  542. for (integer j = 0; j <= numberOfSources; j ++) {
  543. my data [i + 1] [j + 1] = delta [i] [j];
  544. }
  545. }
  546. if (out_directions) {
  547. autoTableOfReal him = EditDistanceTable_to_TableOfReal (me);
  548. for (integer i = 0; i <= numberOfTargets; i ++) {
  549. for (integer j = 0; j <= numberOfSources; j ++) {
  550. his data [i + 1] [j + 1] = psi [i] [j];
  551. }
  552. }
  553. *out_directions = him.move();
  554. }
  555. } catch (MelderError) {
  556. Melder_throw (me, U": minimum path not found.");
  557. }
  558. }
  559. autoTableOfReal EditDistanceTable_to_TableOfReal (EditDistanceTable me) {
  560. try {
  561. autoTableOfReal thee = TableOfReal_create (my numberOfRows, my numberOfColumns);
  562. thy columnLabels. copyElementsFrom (my columnLabels.get());
  563. thy rowLabels. copyElementsFrom (my rowLabels.get());
  564. matrixcopy_preallocated (thy data.get(), my data.get());
  565. return thee;
  566. } catch (MelderError) {
  567. Melder_throw (me, U": no TableOfReal created.");
  568. }
  569. }
  570. /* End of file EditDistanceTable.cpp */