2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Энергия ошибки
Сообщение07.10.2019, 02:22 
Аватара пользователя


21/09/14
25
Дано верное слово и ошибочное. Известен ли алгоритм с помощью которого можно посчитать сколько должно быть пропусков, лишних букв и замен чтобы верное слово превратилось в ошибочное и чтобы сумма таких мутаций была минимальной? Естественно тупой перебор всех мутаций верного слова не интересует.

 Профиль  
                  
 
 Re: Энергия ошибки
Сообщение07.10.2019, 02:36 
Заслуженный участник
Аватара пользователя


30/01/06
72407
Это называется "расстояние Хэмминга" (по Хэммингу, Hamming distance). Гуглите.

 Профиль  
                  
 
 Re: Энергия ошибки
Сообщение07.10.2019, 07:00 
Заслуженный участник


04/05/09
4582
Расстояние Хэмминга - это без вставок, а вам нужно расстояние Левенштейна (Levenshtein distance).

 Профиль  
                  
 
 Re: Энергия ошибки
Сообщение07.10.2019, 12:37 
Заслуженный участник


18/01/15
3073
Как говорит Википедь, расстояние Левенштейна может быть найдено за квадратичное время. Статью из википедии я не смотрел, алгоритма соответствующего не знаю. Но из общих соображений мне кажется, что должен существовать какой-то менее сложный алгоритм, скажем сложности $O(N(d+1))$, где $N$ --- длина слова, а $d$ --- расстояние.

Квадратичные алгоритмы они хоть и полиномиальные, но все же квадратичная сложность --- это слишком долго. Для такого очевидного практического применения, как анализ геномов, квадратичные алгоритмы оказались бы неосуществимы. (Если, скажем, надо сравнить два генома порядка по $10^8$ оснований (не знаю сколько там на самом деле...), то потребовалось бы время порядка $10^{16}$, что нереалистично.

Поэтому я думаю, что в исследование этой задачи уже наверняка вложены немалые усилия, надо только порыть литературу.

 Профиль  
                  
 
 Re: Энергия ошибки
Сообщение07.10.2019, 12:49 
Заслуженный участник
Аватара пользователя


15/10/08
11533
Курить после слова "память".

 Профиль  
                  
 
 Re: Энергия ошибки
Сообщение07.10.2019, 15:38 
Заслуженный участник
Аватара пользователя


16/07/14
8336
Цюрих
vpb в сообщении #1419519 писал(а):
Но из общих соображений мне кажется, что должен существовать какой-то менее сложный алгоритм, скажем сложности $O(N(d+1))$, где $N$ --- длина слова, а $d$ --- расстояние.
Да понятно какой - т.к. между словами, отличающиесемя по длине больше чем на $d$, расстояние больше $d$, достаточно в динамике по префиксу первого слова учитывать только $2d + 1$ вариантов префикса второго.

 Профиль  
                  
 
 Re: Энергия ошибки
Сообщение09.10.2019, 05:27 
Аватара пользователя


21/09/14
25
venco в сообщении #1419493 писал(а):
расстояние Левенштейна (Levenshtein distance).


Кажется то что нужно. Спасибо.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group