Алгоритмы. Опечаточное — микросекунды

Далее под катом очередные технические размышления и эксперименты на тему исправления опечаток.

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

Последние эксперименты показывают разброс от 50 до 4800 микросекунд (или от 0.05 до 4.8 миллисекунд) при среднем времени проверки в 997 микросекунд для словаря в 100 000 слов. Для словарей большего размера это изменится не сильно, поскольку CPU тут используется минимально, только проверки по статическим предрасчитанным индексам.

Всё это с оговорками что алгоритм неоптимизирован и его реализация на C должна быть быстрее разав в 2-3, равно как и отказ от юникода. А то есть цифры в 0.02-2 ms являются вполне достижимыми.

Минус в другом — формирование одного такого индекса на 100 000 слов занимает около 12 часов на персональном компьютере вроде моего с AMD Turion’ом, а сам индекс является вероятностным и эти цифры показывает лишь в 30-50% случаев. Для словаря в 5 000 000, по предварительным оценкам, время расчётов займёт около 1 года на тех же средствах и с той же вероятностью, но для индекса с 10% вероятностью это будут те же 12 часов. Всё это с учётом ручного подбора «ключей» — специальной комбинации метрик которых могут быть тысячи и пока они на уровне эмпирических знаний.

При том что индексов может быть более одного и то что их построение  можно завязать на структуру словаря и структуру входящего потока данных опечаток, то, в итоге, 5-6 таких индексов смогут покрыть до 95% всех вариантов и обеспечивать скорость проверки до 0.02-1 ms со среднием временем в 0.2ms. Сами индексы при этом не более чем в 2 раза превышают размер словаря. То есть для словаря объёмом в 6 мегабайт один индекс составит 12 мегабайт. 6 таких индексов займут 72 мегабайта соответственно. Для 5 000 000 слов оценки будут иными ибо зависимость там ниже линейной, но всяко в пределах 1.5-4 раза.

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

А кластер из PS3  — это мысль. В отличии от покупке времени на EC2 для математических задач он должен быть лучше приспособлен.

About This Author

Яндекс.Метрика