Pull to refresh

Comments 49

Проглядев статью по диагонали заинтересовался, сейчас буду вдумчиво вчитываться. Посмотрев пример немного удивился тому, что слово «cheeazburger» исправило на «hamburger». Разумно, не спорю, но почему же не «cheeseburger»?
«It has a taste of it's own» :)
Видимо, дело в небольшом словаре, где просто нет слова cheesburger. Кроме того, языковая модель, которую я использовал, основана на гутенберговской библиотеки, где тексты 70+ лет давности.
Но, конечно, это меня не оправдывает :).
На самом деле, я даже несколько поразился «разумности» системы. В хорошем смысле. Так что, имхо сделано гораздо лучше, чем могло бы быть. Действительно, если бы он просто исправил на «cheesburger», это было бы слишком ожидаемо и скучно! Выглядит интеллектуально засчет того, что с точки зрения компьютерной системы — это абсолютно разные слова, а вот с точки зрения человека — очень близкие понятия. И такое поведение придало ей в определенном смысле человечности.
Похоже, не нужно было писать коммент. Потом бы всем рассказывал что создал сильный ИИ :).

Конечно, тут просто совпало. Он исправил три ошибки, выбрав самую вероятную гипотезу.
Будем считать, я не видел эти комментарии. Жду от тебя статью про ИИ:)
Шутки шутками, но взвешенные автоматы эквиваленты модальной логике второго порядка (MSO-logic). Так что может что-то получится смастерить в этом направлении.
Удачных изысканий!
Статья очень хорошая, спасибо вам. Всегда было интересно где и над чем работают люди, которые разбираются в подобных задачах, не могли бы вы ответить? =)
Рад, что понравилось. Относительно вашего вопроса — это не гугл и не яндекс. Работаю в небольшой софтовой конторе. Занимаюсь всем: от программирования до маркетинга. А эта тематика — просто хобби последний трех лет. Но чувствую, что это хобби перерастает во что-то большее.
Для поиска в проектах использую Sphinx, жаль, что в нем нет полноценной поддержки функционала «возможно вы имели в виду»
Хотя сейчас погуглил и нашел вот это, нужно попробовать
Такие штуки не просто запихнуть в коробочные продукты. И дело даже не в сложности разработки. Просто сложно сделать универсальный чекер: это сильно зависит от задачи. Для корректировки поисковых запросов нужно одно, для исправления по тексту -другое и т.п.
expertsexchange — сразу бросилось в глаза expert sex change. Видимо, это трюк :)
А заголовок статьи, значит, вам в глаза не бросился!? Да!?
Какая всё-таки у человека избирательная внимательность…
Кстати, совсем не заметил %)
эксперт, секс, мелочь… хм…
Вот смотрите. «multi pi city» не исправляется вообще, и это наверное правильно. Но уже «multi pli city» исправляется на «multiplicity». Почему? Вроде как «multi pli city» гораздо ближе к тому же «multi pi city», нет?
По мне преобразование multi pli city -> multiplicity вполне корректно. Но вообще, разница такая возникает из-за различия весов в исправлении ошибки вставки/удаления пробела. Это можно варьировать, меняя веса.
Тут необходим мощный семантический анализатор. Потому как «по факту» слова «Multi Pi City» написаны правильно, и словоформы друг к другу подходят. Т
Ну, семантика это отдельная тема, и очень непростая. Разве что тренироваться на wordnet'е, да и то, будет неточно.
Здесь даже синтаксиса и морфологии нет в обычном понимании. Но, хотя, последний довольно просто прикрутить.
Хмм… а есть ли примеры пар слово_с_ошибкой-слово_без_ошибки? Этакий полигон для проверки систем коррекции ошибок.
Просто интересно, насколько такой подход работает лучше/хуже чем тот, что на основе языковых моделей, который описан у Рассела Норвига?
Он не Рассел, он Питер :). Рассел — это другой хороший мужик, кто с ним книжку написал.

Я не тестировал, руки не дошли. Но тестовый набор у меня есть, возможно прогоню тесты. Кстати, вот тут выложены полезные файлы norvig.com/ngrams/. Но тут имеет смысл сравнивать проверку по отдельным словам: тот корректор, что описан у него в статье не обращает внимание на контекст, и работает только с отдельными словами. Я пытаюсь исправить набор слов.
«Penis Land» — страна пенисов.
У автора хорошее чувство юмора
Не знаю, в чем юмор.
А вот сайту ручек не позавидуешь.
Блин, забыл ссылку вставить )
www.penisland.net/
Наминусовали, умнички, чмоке вам )
Да, это и имелось ввиду ). Исправляю минус.
Не заставляйте пользователя думать!
Каждый мыслит в меру своей распущености!
Pen island или Penis land — а вы как прочитали в первый раз?
Только вот ники у авторов (lightcaster и light) думаю не совпадение )
Знаю, что один и тот же человек, только это не важно. В правилах четко указано: даже если вы вставляете свой материал, который уже где-то есть — это нарушение.

Материал, кстати, великолепный, — автору спасибо.
Оставим право судить тем, кто за этим следит, сами же будем радоваться хорошей статье. Сроду бы не заинтересовался бы такими вещами, если бы не хабр. Есть даже проект, в котором можно все это попробовать )
Да, есть такое, часть текста из моей статьи. Но это из лучших побуждений. Если бы поставил просто линк, пост вышел бы скомканным и непонятным.
А небольшой словарь — это какой? Как будет работать данный метод на словаре, скажем, 20000 слов? По статье — очень понравилась )
Сейчас словарь — 30 000 слов, в скомпилированном виде — 13Мб. Модель языка — что-то около 10Мб, правда о-очень ужатая (в смысле, сознательно пошел на снижение точности для экономии ресурсов).

Можно создать словарь и для 300 000 слов, но ресурсов для обсчета и выполнения нужно больше. Алгоритмы очень любят есть память.
Я что-то не понял. Навскидку вы меняете алтогритм с O(n*m) на O(n^2*log(n))
и да, для спелчекера важно учитывать транспозицию символов.
Со сложностью не совсем так.

Нужно выполнить две операции: композицию преобразователей и поиск кратчайшего пути в результирующем преобразователе.

Сложность композиции: O(V1V2D1(logD2+M2))
V1,V2 — количество состояний первой и второй машины, D1,D2 — максимальное количество исходящих дуг, M2 — мера недерминизма второго трансдьюсера, т.е. максимальное количество дуг, имеющих одинаковую входную метку, и разные исходящие.

Это было бы слишком долго по времени, но есть возможность не проводить полностью композицию сразу, а делать это лениво. Т.е. проводить композицию уже на этапе поиска пути, постепенно «расширяя» трансдьюсер. Таким образом, все элементы в формуле выше будут гораздо меньше. Т.е. только те, по которым мы «проходимся» в результате композиции.

Время поиска кратчайшей строки для тропического полукольца как у алгоритма Дейкстры: O(|E| + |V|log|V|)

— В идеальном варианте, когда ДКА детерминирован, мы получаем линейное время от длины строки. Но тут у нас не-функциональный преобразователь. Т.е. из одной и той же вершины могут выходить (a,a), (a,b), (a,c),… т.е. входящий символ один и тот же. И детерминировать такую штуку никак нельзя, т.е. мы вынуждены работать недетерминированным автоматом.
постепенно расширяя вы можете нарваться на субоптимальный путь типа
пано рама -> панно рама или нано рама, хотя правильно панорама
Нет, не могу. Не забывайте, я ищу путь с минимальным весом, при этом веса не могут быть отрицательны. На каждом шаге поиска алгоритм расширяет автомат до границ минимального пути. Т.е. если в конце пути мы нарвемся на большой вес, то вдоль всего пути мы будем расширять ответвления, пока не найдем новый минимальный путь, либо не убедимся, что данный путь и есть минимальный.

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

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

Хотя величины там небольшие — надо бы считать сложность с младшими членами и константой…
Оптимизация по сравнению с чем? Я не заявляю, что изобрел более эффективный способ расчета расстояния Левенштейна. Я использую то же самое динамическое программирование, просто взгляд с другой стороны. И по сложности оно должно быть ровно таким же.

Определенная оптимизация по сравнению с полным перебором словаря может быть в том, что я упаковываю этот словарь, делаю минимальным. Хотя тоже самое можно сделать и классическими методами (Витерби, если не ошибаюсь).
Кроме того, результирующий автомат раздувается только в худшем случае. И это «раздутие» можно ограничить. К примеру, задав определенное количество возможных ошибок в автомате E.

Вспомните о моей задаче. Преимущество в том, что я работаю с автоматами, и это просто. Это позволяет совместить разные модели воедино. Традиционный подход в лингвистике: отобрать вероятные гипотезы на уровне морфологии, отобрать наиболее вероятные гипотезы на уровне синтаксиса, попробовать вытащить гипотезы используя спелчекер. Каждый уровень — отдельная программа со своим алгоритмом. Здесь же можно слить все вместе, и получить готовый спелчекер, распознаватель голоса, распознаватель паттернов. При этом каждая из гипотез будет рассматриваться на всем пути обработки, и более того, реализовать это — просто.

Кстати, этот придумал не я, вот линк. Там есть и формальные оценки сложности для разных алгебраических структур.
Да, прошу прощения, я забыл про словарь.
С ним конечно автоматы выглядят привлекательно.
А, да, на счет спелчекера — он учитывает транспоцицию :).

Я просто не рассказал это в статье, чтоб не перегружать. Если хотите — вышлю картинку модели ошибок.
На похожем принципе построена реализация морфологи от AOT aot.ru/docs/sokirko/Dialog2004.htm. Так же там есть ссылка на статью (an Daciuk, Bruce Watson, and Richard Watson, Incremental Construction of Minimal Acyclic Finite State Automata and Transducers), где описывается инкрементальное построение автомата, для проверки правильности написания слова. Для всех русской морфологии размер автомата будет около 400 тысяч вершин и около 850 тысяч переходов.
Да, вы правы. Там похожая штука, с тем отличием что там не трансдьюсер, а акцептор. Это позволяет искать слова в словаре за линейное время. А статейка и правда неплохая, там рассказывается как в эту штуку добавить строку, сохраняя детерминированность.
Only those users with full accounts are able to leave comments. Log in, please.