Здравствуйте, rp80, Вы писали:
R>Есть Большой словарь правильных слов. Пользователь вводит свое слово и может ошибиться, но так что длина слова будет не более чем на 2 символа больше или на 2 меньше , чем правильное написание. Нужно быстро пройтись по словарю и, если точного совпадения нет выдать слова такие что, расстояние Левенштейна между ними и введенным словом не более некоторой константы.
R>Алгоритм поиска расстояния Левенштейна реализован и вроде более менее оптимизирован. И, собственно, остается организовать быстрый поиск поиск по словарю. А конкретнее задача в том как сузить область поиска, чтобы не пришлось перебирать все слова в словаре.
R>Словарь грузится в std::unordered_set.
R>Пока в голову пришли 2 варианта.
R>1. При загрузке словаря разбить все слова на непересекающиеся группы по длине слова. А так как введенное слово не может быть более чем на 2 символа меньше или больше правильного, то нужно искать не во всем словаре а только в группах с таким же кол-вом слов, а также в -1 -2 и в +1 +2.
R>2. Разбивать слова в словаре на подгруппы по 2 или 3 символа, например машина = маш, аши, шин, ина, эти подгруппы будут индексами. Ну и соответственно, когда вводим слово, также бить его на подгруппы и искать далее только в тех подразделах словаря, где есть одинаковые подгруппы. Это решение мне кажется более подходящим, кроме одного но. При первоначальном разбиении многие слова будут дублироваться, например слово "камасутра" будет и в группе "кам" вместе с "камчатка" и в группе "утр" вмсте с "утро" и размер словаря сильно вырастет, возможно в несколько раз.
R>В общем, прошу совета по алгоритму, ну и может где почитать про это. Спасибо.
Тестовое задание в CQG пишешь?
Знаю решение этой задачки. Идея в общем такая: нужно проиндексировать словарь по хешам. Хеши соответствуют префиксам и суффиксам искомого слова. Как конкретно образуются префиксы и суффиксы — нужно расписать на бумаге все возможные случаи, в зависимости от точных условий твоей задачи. А дальше ищешь слово в группах, которые содержат хеши, полученные из твоего слова. Сначала, разумеется, нужно проверить слово в словаре на точное совпадение. Думай, в общем.
