расстояние Левенштейна -> Форум на Исходниках.Ру

	Наши проекты: Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту

Здравствуйте, Гость ! [3.129.247.196]

правила раздела Алгоритмы

1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке

Модераторы: Akina, shadeofgray

Новое голосование

расстояние Левенштейна

experimenter

Сообщ. #1 , 07.10.07, 10:19

Master

Профиль · PM

Поощрения: 2 Dgm

Рейтинг (т): 26

Привет всем.
Как можно реализовать программу по вычислению расстояния Левенштейна с линейным требованием памяти? Т.е. само вычисление - понятно, что за счёт использования всего двух строк таблицы, можно сделать линейным по требованию к памяти, а вот нахождение самих действий над словом, которое ищется при помощи бэктрэкинга, я не могу понять, можно ли сделать линейным по требованию к памяти. Даже если использовать 2 строки и хранить сам путь в каждой ячейке вместе с расстоянием, то всё равно получается квадратичное требование к памяти на последнем шаге, что печально.

Спасибо заранее за соображения.

Сообщение отредактировано: experimenter - 07.10.07, 10:20

ors_archangel

Сообщ. #2 , 10.10.07, 18:54

Senior Member

Профиль · PM

На http://algolist.manual.ru есть алгоритм Машека и Патерсона, который, если я правильно понял, можно применить для нахождения расстояния Левенштейна с асимптотической вычислительной сложностью O(n) и асимпотическими требованиями по памяти O(n² / log n)...

Сообщение отредактировано: ors_archangel - 10.10.07, 18:56

experimenter	Сообщ. #3 , 11.10.07, 07:35
Master Профиль · PM Поощрения: 2 Dgm Рейтинг (т): 26	Спасибо! Надо глянуть. Добавлено 11.10.07, 07:36 Цитата experimenter @ 11.10.07, 07:35 Спасибо! Надо глянуть. Да, алгоритм чуть посложнее будет, чем у Левенштейна...

Eric-S

Сообщ. #4 , 06.12.07, 04:21

Profi

Профиль · PM

Ух! Мясо! Ничерта не понял. Если ещё часа два помучаюсь, может до меня начнёт конечно доходить смысл. Я даже написал свою версию функции Левенштейна, причем она даже работала, но Алгоритм Машека и Патерсона, до меня пока не доходит.

Посоветуйте пожалуйста что почитать, в инете на русском можно, на эту тему?! Лучше с азов. Я имею в виду математическую лингвистику.

0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)

0 пользователей:

[ Script execution time: 0,0625 ] [ 15 queries used ] [ Generated: 28.04.24, 04:55 GMT ]