Комментарии 25
НЛО прилетело и опубликовало эту надпись здесь
Только сдал экзамен по информатике, но все равно спасибо за интересную статью :) кстати, я тоже с физтеха)
Отличный пост! Спасибо.
Аха-Корасика да, можно)
Аха-Корасика да, можно)
Раз появились желающие… Но вообще-то я считаю, что алгоритм Ахо-Корасика более простой, чем Укконен, да и найти его описание тоже можно в больших местах. Но вот алгоритм Укконена я долго не мог найти, за исключением возможно всего пары мест: Ден Гасфилд «Строки, деревья и последовательности в алгоритмах» (причём там не очень понятно написано, и для тех, кто решил ознакомится с этим алгоримом впервые, будет сложно разобраться в нём), и как ниже указано, есть конспект Лифшица, но который я раньше не встечал. Поэтому и решил, что ещё одно описание алгоритму Укконена будет не лишним, что не могу сказать об алгоритме Ахо-Корасика.
PS. Возможно, через недельку-две смогу написать и про Ахо-Корасика.
PS. Возможно, через недельку-две смогу написать и про Ахо-Корасика.
Мне кажется, имеет смысл добавить ссылку на оригинал алгоритма и на конспект Юрия Лифшица.
Также надо учитывать, что решение зависит линейно от размера a алфавита (O(na) ). В отличие от, например, суффиксного массива.
Также надо учитывать, что решение зависит линейно от размера a алфавита (O(na) ). В отличие от, например, суффиксного массива.
А может кто-то выложит полные лекции годного универа (типа МФТИ) по Computer Science? Было бы здорово. Уверен, многие бы скачали и почитали.
Я не в праве выкладывать такую информацию. Считаю, что это работа преподавателей, и им решать, где и что они хотят выложить в общественное пользование. Ведь у каждого ВУЗа есть свои секреты
Сайт итмо по вики-конспектам
По крайней мере, думаю, вас заинтересуют алгоритмы 1-2, а также 3-4 семестров
По крайней мере, думаю, вас заинтересуют алгоритмы 1-2, а также 3-4 семестров
Неплохо бы привести графические схемы и примеры. Так будет нагляднее и понятнее.
Когда писал библиотеку для поиска фраз в тексте, остановился на суффиксном массиве, так как он эффективно решал мою задачу и при этом оказался гораздо проще суффиксного дерева в понимании. Интересно, на сколько суффиксное дерево лучше/хуже суффиксного массива в плане скорости поиска строки в тексте по готовому дереву/массиву?
Если Вы строите массив за линейное время (например, алгоритм Фарача), то он лучше — время и память не зависят от размера алфавита. Особенно важно последнее обстоятельство. Но это нетривиальный алгоритм. Тот алгоритм построения массива, который чаще встречается и проще в реализации, строит за 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
Задча: найти наиболее близкие к образцу цепочки.
Может быть, кто-нибудь предложит тогда хороший алгоритм поиска похожего слова: например, у нас есть 1 млн. слов, на вход подается слово, похожее на одно (или несколько) из них, задача найти на какие. Естественно, тупо перебирать и считать для каждой пары editing distance или похожую функцию неэффективно.
Или, если упростить эту задачу: имеем цепочки чисел от 1 до N, где N в пределах 1000, выстроенных по возрастанию:
1 4 56 67
1 3 35 56 145
1 2 3
И на вход алгоритма подаем цепочку, к примеру 1 4 23 56 67
Задча: найти наиболее близкие к образцу цепочки.
Хорошая статья!
Просто ради интереса — а тебе ведь в ЛКШ рассказали этот алгоритм?
Теперь можно еще и про суффиксный автомат рассказать — он сложнее для понимания, зато пишется очень просто и работает весьма быстро!:)
Просто ради интереса — а тебе ведь в ЛКШ рассказали этот алгоритм?
Теперь можно еще и про суффиксный автомат рассказать — он сложнее для понимания, зато пишется очень просто и работает весьма быстро!:)
> Очевидно, что сумма длин всех суффиксов строки пропорциональна квадрату длины самой строки.
Может кубу? Количество суффиксов — N^2, длина — N.
Может кубу? Количество суффиксов — N^2, длина — N.
Если бы был указан список задач где можно решить етим алгоритмом — было бы замечательно!
Если кому-то интересно, сейчас появился алгоритм построения суффиксного дерева по-проще — это модификация старого алгоритма Вейнера. Можно посмотреть тут: habrahabr.ru/post/258121 (с исходником) или тут www.youtube.com/watch?v=q9bPAVSmzfA
Короткую реализацию алгоритма Укконена можно найти тут: codeforces.com/blog/entry/16780?locale=ru
Короткую реализацию алгоритма Укконена можно найти тут: codeforces.com/blog/entry/16780?locale=ru
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Построение суффиксного дерева: алгоритм Укконена