Здравствуйте, rp80, Вы писали:
R>Пользователь вводит свое слово и может ошибиться, но так что длина слова будет не более чем на 2 символа больше или на 2 меньше , чем правильное написание. Нужно быстро пройтись по словарю и, если точного совпадения нет выдать слова такие что, расстояние Левенштейна между ними и введенным словом не более некоторой константы.
При пользовательском вводе часто бывают транспозиции символов. Для таких отслеживания таких ошибок есть расстояние Дамерау — Левенштейна, например.
R>2. Разбивать слова в словаре на подгруппы по 2 или 3 символа, например машина = маш, аши, шин, ина, эти подгруппы будут индексами. Ну и соответственно, когда вводим слово, также бить его на подгруппы и искать далее только в тех подразделах словаря, где есть одинаковые подгруппы. Это решение мне кажется более подходящим, кроме одного но. При первоначальном разбиении многие слова будут дублироваться, например слово "камасутра" будет и в группе "кам" вместе с "камчатка" и в группе "утр" вмсте с "утро" и размер словаря сильно вырастет, возможно в несколько раз.
Ну так хранить нужно не сами слова, а ссылки на них в виде индекса в глобальном массиве слов. Будет тратится [log₂N] бит на каждое вхождение слова. Хотя, конечно, индекс все равно растёт.
R>В общем, прошу совета по алгоритму,
Их простых подходов — хранить все слова в TRIE (или в DAWG для экономии памяти). Тогда процедура поиска слова в trie с k ошибками будет выглядеть так:
Если k == 0, то делается точный поиск (который может завершиться успехом или нет).
Если k > 0, то переходим из текущего узла trie по всем ссылкам, и если переход по ссылке был по несовпадающей букве, уменьшаем k.
Такой рекурсивный алгоритм найдёт все слова с указанным ограничением на расстояние Левенштейна без явного его вычисления для каждого слова с нуля. Собственно trie часто используется для подсчёта расстояния до всех слов — это известный алгоритм. Тут лишь отличие в том, что если для какого-то узла trie уже установлено, что расстояние превысило k, то это означает, что и у всех дочерних узлов оно не меньше, а это отсекает большое число слов, которые уже можно не проверять.
R>ну и может где почитать про это.
Есть отличный обзор "Indexing Methods for Approximate Dictionary Searching: Comparative Analysis".
Либо просто смотреть как работают известные программы проверки орфографии вроде aspell (или даже сразу задействовать их).
Есть Большой словарь правильных слов. Пользователь вводит свое слово и может ошибиться, но так что длина слова будет не более чем на 2 символа больше или на 2 меньше , чем правильное написание. Нужно быстро пройтись по словарю и, если точного совпадения нет выдать слова такие что, расстояние Левенштейна между ними и введенным словом не более некоторой константы.
Алгоритм поиска расстояния Левенштейна реализован и вроде более менее оптимизирован. И, собственно, остается организовать быстрый поиск поиск по словарю. А конкретнее задача в том как сузить область поиска, чтобы не пришлось перебирать все слова в словаре.
Словарь грузится в std::unordered_set.
Пока в голову пришли 2 варианта.
1. При загрузке словаря разбить все слова на непересекающиеся группы по длине слова. А так как введенное слово не может быть более чем на 2 символа меньше или больше правильного, то нужно искать не во всем словаре а только в группах с таким же кол-вом слов, а также в -1 -2 и в +1 +2.
2. Разбивать слова в словаре на подгруппы по 2 или 3 символа, например машина = маш, аши, шин, ина, эти подгруппы будут индексами. Ну и соответственно, когда вводим слово, также бить его на подгруппы и искать далее только в тех подразделах словаря, где есть одинаковые подгруппы. Это решение мне кажется более подходящим, кроме одного но. При первоначальном разбиении многие слова будут дублироваться, например слово "камасутра" будет и в группе "кам" вместе с "камчатка" и в группе "утр" вмсте с "утро" и размер словаря сильно вырастет, возможно в несколько раз.
В общем, прошу совета по алгоритму, ну и может где почитать про это. Спасибо.
31.03.13 16:41: Перенесено модератором из 'C/C++. Прикладные вопросы' — Кодт
Здравствуйте, rp80, Вы писали:
R>Есть Большой словарь правильных слов. Пользователь вводит свое слово и может ошибиться, но так что длина слова будет не более чем на 2 символа больше или на 2 меньше , чем правильное написание. Нужно быстро пройтись по словарю и, если точного совпадения нет выдать слова такие что, расстояние Левенштейна между ними и введенным словом не более некоторой константы.
R>Алгоритм поиска расстояния Левенштейна реализован и вроде более менее оптимизирован. И, собственно, остается организовать быстрый поиск поиск по словарю. А конкретнее задача в том как сузить область поиска, чтобы не пришлось перебирать все слова в словаре. R>Словарь грузится в std::unordered_set. R>Пока в голову пришли 2 варианта.
R>1. При загрузке словаря разбить все слова на непересекающиеся группы по длине слова. А так как введенное слово не может быть более чем на 2 символа меньше или больше правильного, то нужно искать не во всем словаре а только в группах с таким же кол-вом слов, а также в -1 -2 и в +1 +2.
R>2. Разбивать слова в словаре на подгруппы по 2 или 3 символа, например машина = маш, аши, шин, ина, эти подгруппы будут индексами. Ну и соответственно, когда вводим слово, также бить его на подгруппы и искать далее только в тех подразделах словаря, где есть одинаковые подгруппы. Это решение мне кажется более подходящим, кроме одного но. При первоначальном разбиении многие слова будут дублироваться, например слово "камасутра" будет и в группе "кам" вместе с "камчатка" и в группе "утр" вмсте с "утро" и размер словаря сильно вырастет, возможно в несколько раз.
R>В общем, прошу совета по алгоритму, ну и может где почитать про это. Спасибо.
Тестовое задание в CQG пишешь?
Знаю решение этой задачки. Идея в общем такая: нужно проиндексировать словарь по хешам. Хеши соответствуют префиксам и суффиксам искомого слова. Как конкретно образуются префиксы и суффиксы — нужно расписать на бумаге все возможные случаи, в зависимости от точных условий твоей задачи. А дальше ищешь слово в группах, которые содержат хеши, полученные из твоего слова. Сначала, разумеется, нужно проверить слово в словаре на точное совпадение. Думай, в общем.
Здравствуйте, opener, Вы писали:
O>Здравствуйте, rp80, Вы писали:
R>>Есть Большой словарь правильных слов. Пользователь вводит свое слово и может ошибиться, но так что длина слова будет не более чем на 2 символа больше или на 2 меньше , чем правильное написание. Нужно быстро пройтись по словарю и, если точного совпадения нет выдать слова такие что, расстояние Левенштейна между ними и введенным словом не более некоторой константы.
R>>Алгоритм поиска расстояния Левенштейна реализован и вроде более менее оптимизирован. И, собственно, остается организовать быстрый поиск поиск по словарю. А конкретнее задача в том как сузить область поиска, чтобы не пришлось перебирать все слова в словаре. R>>Словарь грузится в std::unordered_set. R>>Пока в голову пришли 2 варианта.
R>>1. При загрузке словаря разбить все слова на непересекающиеся группы по длине слова. А так как введенное слово не может быть более чем на 2 символа меньше или больше правильного, то нужно искать не во всем словаре а только в группах с таким же кол-вом слов, а также в -1 -2 и в +1 +2.
R>>2. Разбивать слова в словаре на подгруппы по 2 или 3 символа, например машина = маш, аши, шин, ина, эти подгруппы будут индексами. Ну и соответственно, когда вводим слово, также бить его на подгруппы и искать далее только в тех подразделах словаря, где есть одинаковые подгруппы. Это решение мне кажется более подходящим, кроме одного но. При первоначальном разбиении многие слова будут дублироваться, например слово "камасутра" будет и в группе "кам" вместе с "камчатка" и в группе "утр" вмсте с "утро" и размер словаря сильно вырастет, возможно в несколько раз.
R>>В общем, прошу совета по алгоритму, ну и может где почитать про это. Спасибо.
O>Тестовое задание в CQG пишешь?
Та же мысль возникла
В своем алгоритме я группировал по длине, внутри делал неоптимизированный поиск, в каждом случае выясняя дистанцию.
Но с большим словарем я не проверял. Возможно, данная задача ляжет на дерево и можно будет тогда ускорить.
WM>Ну так хранить нужно не сами слова, а ссылки на них в виде индекса в глобальном массиве слов. Будет тратится [log₂N] бит на каждое вхождение слова. Хотя, конечно, индекс все равно растёт.
WM>Их простых подходов — хранить все слова в TRIE (или в DAWG для экономии памяти). Тогда процедура поиска слова в trie с k ошибками будет выглядеть так: WM>Если k == 0, то делается точный поиск (который может завершиться успехом или нет). WM>Если k > 0, то переходим из текущего узла trie по всем ссылкам, и если переход по ссылке был по несовпадающей букве, уменьшаем k.
WM>Такой рекурсивный алгоритм найдёт все слова с указанным ограничением на расстояние Левенштейна без явного его вычисления для каждого слова с нуля. Собственно trie часто используется для подсчёта расстояния до всех слов — это известный алгоритм. Тут лишь отличие в том, что если для какого-то узла trie уже установлено, что расстояние превысило k, то это означает, что и у всех дочерних узлов оно не меньше, а это отсекает большое число слов, которые уже можно не проверять.
Мм.. а что можете сказать про скорость? Мне кажется я где-то читал, что trie деревья в несколько раз медленнее индексирования по суффиксам
WM>Есть отличный обзор "Indexing Methods for Approximate Dictionary Searching: Comparative Analysis". WM>Либо просто смотреть как работают известные программы проверки орфографии вроде aspell (или даже сразу задействовать их).
Спасибо за статью. А аспел по внешнему виду хорошая штука, но дело в том, что мне надо написать всё на чистом С и желательно покороче. В С++ я только делаю наброски.
Здравствуйте, saf_e, Вы писали:
O>>Здравствуйте, rp80, Вы писали:
_>В своем алгоритме я группировал по длине, внутри делал неоптимизированный поиск, в каждом случае выясняя дистанцию. _>Но с большим словарем я не проверял. Возможно, данная задача ляжет на дерево и можно будет тогда ускорить.
Ну я так и делал, когда писал это как тестовое задание в CQG. Решил, что с них этого будет достаточно, потому и не прошел.
Если к группировке по длине добавить еще поиск по хешу, количество слов, которые нужно проверить, уменьшается раз так в сто.
Здравствуйте, rp80, Вы писали:
R>Мм.. а что можете сказать про скорость?
Хороший универсальный алгоритм. Лучший из простых. Но можно сделать быстрее.
Я, кстати, путано его рассказал. Если проще, то заранее компилируется trie со словарём. Потом по запросу строится автомат и запускается синхронный поиск в автомате и trie. То есть при посещении узла trie будет известен номер состояния автомата, который ему соответствует, а спускаться к дочерним узлам можно только если и в автомате есть такой же переход. Ответом же станут все слова, до которых удастся спуститься.
А так, должно быть очевидно, что для любого алгоритма из этой области можно подобрать набор данных, на котором его обойдёт другой алгоритм, специально сделанный под этот набор. Идеального алгоритма не существует же. Время работы существенно меняется даже от изменения тематики текста, не говоря уж о более существенных параметрах как язык или количество исправляемых опечаток. Собственно, посмотри обзор.
R>Мне кажется я где-то читал, что trie деревья в несколько раз медленнее индексирования по суффиксам
Непонятно что с чем сравнивали.
А вообще, у trie, как у структуры данных, всё хорошо с производительностью. Но trie — это не алгоритм же. А вот уже алгоритм поиска может разные структуры данных совершенно по разному.
