2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Минимизация расстояния Левенштейна
Сообщение15.02.2017, 17:41 
Дана строка $s$ в алфавите $\Sigma_1$ и строка $t$ в алфавите $\Sigma_2$, требуется найти инъективную функцию $f{:}\,\Sigma_1\rightarrow\Sigma_2$, минимизирующую расстояние Левенштейна (edit distance) между строками $f\!\left(s\right)$ и $t$ (функция $f$ задаёт гомоморфизм на строках). Размеры алфавитов не ограничены.
Что известно об алгоритмах (точных и приближённых) для этой задачи, о её сложности? Есть ли для неё хорошие известные эвристики?

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group