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

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

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

Последние эксперименты показывают разброс от 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

  • tasman

    Интересно было бы узнать какие именно метрики (ключи) использовались. И как именно выбирались. То, что время формирования индекса столь велико позволяет предположить либо некий переборный процесс либо итерационное «самообучение» (автоматическая кластеризация типа SOM или что-то похожее). Если есть возможность — интересно было бы почитать.

  • http://ivan.begtin.name ivbeg

    Где почитать, увы, незнаю — большинство западных исследований идут по принципу построения FSA, или вообще использования Soundex, а не расстояния редактирования.

    Метрики, вернее пути их выбора, я частично раскрыл в следующем посте по регулярным выражениям. Там действительно переборный процесс и многоэтапный map/reduce и кластеризацией даже не самих слов, а именно что метрик.

  • tasman

    То есть идет перебор возможных метрик и дальнейшая «оценка» этих метрик на предмет полезности в предварительной оценке? Было бы интересно узнать подробнее о процессе подбора. Пост на эту тему не планируется?

  • http://ivan.begtin.name ivbeg

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

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