Pull to refresh

Comments 25

UFO just landed and posted this here
Только сдал экзамен по информатике, но все равно спасибо за интересную статью :) кстати, я тоже с физтеха)
Может, вы оба даже с одного курса? :)
А вы, почти наверное, один из наших экзаменаторов и ассистент на факультете :)
Отличный пост! Спасибо.

Аха-Корасика да, можно)
Раз появились желающие… Но вообще-то я считаю, что алгоритм Ахо-Корасика более простой, чем Укконен, да и найти его описание тоже можно в больших местах. Но вот алгоритм Укконена я долго не мог найти, за исключением возможно всего пары мест: Ден Гасфилд «Строки, деревья и последовательности в алгоритмах» (причём там не очень понятно написано, и для тех, кто решил ознакомится с этим алгоримом впервые, будет сложно разобраться в нём), и как ниже указано, есть конспект Лифшица, но который я раньше не встечал. Поэтому и решил, что ещё одно описание алгоритму Укконена будет не лишним, что не могу сказать об алгоритме Ахо-Корасика.

PS. Возможно, через недельку-две смогу написать и про Ахо-Корасика.
Мне кажется, имеет смысл добавить ссылку на оригинал алгоритма и на конспект Юрия Лифшица.

Также надо учитывать, что решение зависит линейно от размера a алфавита (O(na) ). В отличие от, например, суффиксного массива.
А может кто-то выложит полные лекции годного универа (типа МФТИ) по Computer Science? Было бы здорово. Уверен, многие бы скачали и почитали.
Я не в праве выкладывать такую информацию. Считаю, что это работа преподавателей, и им решать, где и что они хотят выложить в общественное пользование. Ведь у каждого ВУЗа есть свои секреты
А контакты кого-нибудь из ваших преподавателей можно в личку? Я б пообщался с ними, возможно они бы поделились своими наработками.
Неплохо бы привести графические схемы и примеры. Так будет нагляднее и понятнее.
Когда писал библиотеку для поиска фраз в тексте, остановился на суффиксном массиве, так как он эффективно решал мою задачу и при этом оказался гораздо проще суффиксного дерева в понимании. Интересно, на сколько суффиксное дерево лучше/хуже суффиксного массива в плане скорости поиска строки в тексте по готовому дереву/массиву?
Если Вы строите массив за линейное время (например, алгоритм Фарача), то он лучше — время и память не зависят от размера алфавита. Особенно важно последнее обстоятельство. Но это нетривиальный алгоритм. Тот алгоритм построения массива, который чаще встречается и проще в реализации, строит за O(NlogN), что медленнее, чем построение дерева.

Вообще, массив вроде как и появился для оптимизации потребления памяти.
О! Интересные темы пошли.

Может быть, кто-нибудь предложит тогда хороший алгоритм поиска похожего слова: например, у нас есть 1 млн. слов, на вход подается слово, похожее на одно (или несколько) из них, задача найти на какие. Естественно, тупо перебирать и считать для каждой пары editing distance или похожую функцию неэффективно.

Или, если упростить эту задачу: имеем цепочки чисел от 1 до N, где N в пределах 1000, выстроенных по возрастанию:

1 4 56 67
1 3 35 56 145
1 2 3

И на вход алгоритма подаем цепочку, к примеру 1 4 23 56 67

Задча: найти наиболее близкие к образцу цепочки.
UFO just landed and posted this here
Хорошая статья!
Просто ради интереса — а тебе ведь в ЛКШ рассказали этот алгоритм?

Теперь можно еще и про суффиксный автомат рассказать — он сложнее для понимания, зато пишется очень просто и работает весьма быстро!:)
Этот алгоритм где мне только не рассказывали, но в ЛКШ тоже было дело. Но идея возникла только сейчас, при подготовке к сессии. А что, про него рассказывали этой зимой?
> Очевидно, что сумма длин всех суффиксов строки пропорциональна квадрату длины самой строки.

Может кубу? Количество суффиксов — N^2, длина — N.
Вы ошиблись. Видимо, вы имели ввиду количество всех «подстрок» N^2. А мы рассматриваем только суффиксы. Суффикс — подстрока, конец которой совпадает с концом нашей строки. Таким образом, суффикс определяется своим началом, которых N
Да, меня сбило с толку то, что в русском языке суффикс не обязательно находится в конце.
А со строковыми алгоритмами почти не работал, так что не привык к этой терминологии.
Если бы был указан список задач где можно решить етим алгоритмом — было бы замечательно!
Если кому-то интересно, сейчас появился алгоритм построения суффиксного дерева по-проще — это модификация старого алгоритма Вейнера. Можно посмотреть тут: habrahabr.ru/post/258121 (с исходником) или тут www.youtube.com/watch?v=q9bPAVSmzfA

Короткую реализацию алгоритма Укконена можно найти тут: codeforces.com/blog/entry/16780?locale=ru
Sign up to leave a comment.

Articles