Как генерировать ошибки для ключевого слова?

Question

[bmc41]

Добрый день, подскажите пожалуйста какую библиотеку можно использовать для генерации ошибок для ключевого слова? Задача - реализовать неточный поиск с использованием алгоритма Ливенштейна. На входе есть 1000 ключевых слов. Нужно для каждого ключевого слова сгенировать ошибки (опечатки, разрывы, подстановки) чтобы сформировать словарь ошибок. Подскажите чем это можно реализовать? Заранее большое спасибо!

Comments

[MinTnt]

Все абсолютно ошибки в словах - всё равно невозможно сгенерировать. Подход мысли нужен другой, а не такой прямой, как кажется

Answer 1

[rPman]

библиотеки такой нет, делать самому, обычным перебором.
- разрывы: цикл по количеству букв в слове - 1: вставить пробел на i-ое место
- повторить если нужно по два, три.. более разрывов в слове, пропуская более одного пробела рядом
- пропуски: то же самое только вместо вставки пробела удаляем символ
- удвоения символов: то же самое только вместо подстановки пробела, подставляем текущий символ
- опечатки и подстановки
в плохом варианте, перебором для каждого допустимого символа делаем то же самое что для пробела
в хорошем варианте, каждому символу задаем список символов, на которые он может быть заменен (соседние на клавиатуре)

в результате на каждое слово будет массив его модификаций.

p.s. не понимаю как все это поможет решению поставленной задачи?

Задача - реализовать неточный поиск с использованием алгоритма Ливенштейна

это алгоритм вполне конкретный и очень простой, в нем нет никаких генераций подстановок и опечаток

Comments

[bmc41]

Да это действительно разные вещи. Алгоритм левенштейна используется для выдачи рекомендаций, словарь используется для выдачи информации по точному совпадению. А вы сможете это реализовать? Если да, то напишите свой тг. Заранее благодарю за ответ.