Техническое. Опечаточное

На днях уже не один раз отвечая на вопросы по алгоритмам выявления и исправления опечаток, я в очередной раз задумался о этой теме.

Собственно в последний раз я остановился на том что расчет расстояния Левенштейна можно значительно ускорить созданием специальных индексов основанных на разнице в расстоянии Левенштейна между словами в словаре.

С того момента у меня было немного времени чтобы вернутся к этой теме, но осталась одна нереализованная идея — распаковка алгоритма расчёта расстояния Левенштейна и реоргганизация хранения словарей для сужения выборок. Не так давно эту идею я всё же опробовал, чтобы понять состоятельность подхода.

Идея достаточно проста, чтобы не намекать дальше — подход тут аналогичен проверки устойчивости криптоалгоритмов по шагам. Главный недостаток в необходимости реляционной базы данных для работы, связано это с тем что структура хранимых данных, псевдо-индекс, значительно усложняется и нужен язык запросов чтобы выборку резко сузить.

С другой стороны, по если в словаре 100 000 слов, то один запрос сквозь распаковывающий фильтр сужает размер выборки требующей проверки до 3000-5000 слов. А то есть до 3-5% или от 20 до 33 раз.

Соответственно время исправления опечатки варьируется от 0,2 до 1,2 секунды на рабочей машине AMD Turion TL-60 2Ghz.

Это без оптимизации непосредственно самого сравнения по алгоритму Левенштейна, например, используя его оптимизированную версию на C или Asm.

Без оптимизации самого распаковывающего алгоритма и стыковки со спец. индексами о которых я писал ранее.

Моё видение что время на исправление опечаток, в конце-концов, можно сократить зо 0,1-0,7 секунд. А для наиболее распространнёных не превышать 0,2 секунд.

Реализация это требует времени, но может быть как исследовательский сервис в виде прилепки к Скиуру я всё таки сделать смогу. Просто для материализации результатов, чтобы было.

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

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

В любом случае это не самая сложная, инженерная задача пригодная чуть ли не для каждодневной оптимизации. Интересной она становится только если начать её сводить к онтологической модели опечаток и вероятностным факторам основанных на этих онтологиях.

Вообще же нужна база хотя бы в 1000 опечаток для проверок чтобы подсчитать метрики.