Здравствуйте, F3V, Вы писали:

F3V>Нужно подготовить два словаря: брендов и опечаток.

На слово-название бренда длиной 8 символов получается более 350 тыс вариантов с опечатками до 2 шт.


F3V>Миллион для таких словарей не много, должно потянуть.

Из миллиона слов получится 350 миллиардов вариантов.
Пусть даже часть опечаток от разных ключевых слов склеятся в один, это не спасёт. ))

Некоторые алгоритмы предлагают подход от обратного — генерить всевозможные опечатки не словаря, а входного токена.

Т.е., алгоритм такой:
— проверили точное соответствие;
— если не нашли, то нагенерили все варианты с одной опечаткой (это замена одной буквы=N*K, где K — размер алфавита, плюс все соседние перестановки=N, плюс все удаления по одному символу=N, т.е. разветвление получается примерно N(K+2) на каждую ошибюку), проверили в цикле все нагенерённые варианты;
— если не нашли, нагенерили из каждого варианта еще варианты, в этом месте и получается более 350 тыс уже при допущении 2-х ошибок.

Далее считается, что 3 ошибки на практике встречаются редко (это уже более 200 млн вариантов от исходного слова) и их лучше не обрабатывать.

Поэтому, в таких системах живёт магическое число 2.

Однако, в реальных системах проверки правописания всё чуть проще, т.к. алфавит намного уже. А названия брендов могут состоять, к примеру, из русских и латинских букв, плюс цифры, плюс различные знаки !-+* и т.д. Т.е. алфавит в разы больше, разветвление на каждой ошибке слишком большое.