Comments 49
Проглядев статью по диагонали заинтересовался, сейчас буду вдумчиво вчитываться. Посмотрев пример немного удивился тому, что слово «cheeazburger» исправило на «hamburger». Разумно, не спорю, но почему же не «cheeseburger»?
Видимо, дело в небольшом словаре, где просто нет слова cheesburger. Кроме того, языковая модель, которую я использовал, основана на гутенберговской библиотеки, где тексты 70+ лет давности.
Но, конечно, это меня не оправдывает :).
Но, конечно, это меня не оправдывает :).
На самом деле, я даже несколько поразился «разумности» системы. В хорошем смысле. Так что, имхо сделано гораздо лучше, чем могло бы быть. Действительно, если бы он просто исправил на «cheesburger», это было бы слишком ожидаемо и скучно! Выглядит интеллектуально засчет того, что с точки зрения компьютерной системы — это абсолютно разные слова, а вот с точки зрения человека — очень близкие понятия. И такое поведение придало ей в определенном смысле человечности.
Статья очень хорошая, спасибо вам. Всегда было интересно где и над чем работают люди, которые разбираются в подобных задачах, не могли бы вы ответить? =)
Рад, что понравилось. Относительно вашего вопроса — это не гугл и не яндекс. Работаю в небольшой софтовой конторе. Занимаюсь всем: от программирования до маркетинга. А эта тематика — просто хобби последний трех лет. Но чувствую, что это хобби перерастает во что-то большее.
Для поиска в проектах использую 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» написаны правильно, и словоформы друг к другу подходят. Т
Хмм… а есть ли примеры пар слово_с_ошибкой-слово_без_ошибки? Этакий полигон для проверки систем коррекции ошибок.
Просто интересно, насколько такой подход работает лучше/хуже чем тот, что на основе языковых моделей, который описан у Рассела Норвига?
Просто интересно, насколько такой подход работает лучше/хуже чем тот, что на основе языковых моделей, который описан у Рассела Норвига?
Он не Рассел, он Питер :). Рассел — это другой хороший мужик, кто с ним книжку написал.
Я не тестировал, руки не дошли. Но тестовый набор у меня есть, возможно прогоню тесты. Кстати, вот тут выложены полезные файлы norvig.com/ngrams/. Но тут имеет смысл сравнивать проверку по отдельным словам: тот корректор, что описан у него в статье не обращает внимание на контекст, и работает только с отдельными словами. Я пытаюсь исправить набор слов.
Я не тестировал, руки не дошли. Но тестовый набор у меня есть, возможно прогоню тесты. Кстати, вот тут выложены полезные файлы norvig.com/ngrams/. Но тут имеет смысл сравнивать проверку по отдельным словам: тот корректор, что описан у него в статье не обращает внимание на контекст, и работает только с отдельными словами. Я пытаюсь исправить набор слов.
«Penis Land» — страна пенисов.
У автора хорошее чувство юмора
У автора хорошее чувство юмора
Не заставляйте пользователя думать!
Каждый мыслит в меру своей распущености!
Pen island или Penis land — а вы как прочитали в первый раз?
Каждый мыслит в меру своей распущености!
Pen island или Penis land — а вы как прочитали в первый раз?
Только вот ники у авторов (lightcaster и light) думаю не совпадение )
Да, есть такое, часть текста из моей статьи. Но это из лучших побуждений. Если бы поставил просто линк, пост вышел бы скомканным и непонятным.
А небольшой словарь — это какой? Как будет работать данный метод на словаре, скажем, 20000 слов? По статье — очень понравилась )
Сейчас словарь — 30 000 слов, в скомпилированном виде — 13Мб. Модель языка — что-то около 10Мб, правда о-очень ужатая (в смысле, сознательно пошел на снижение точности для экономии ресурсов).
Можно создать словарь и для 300 000 слов, но ресурсов для обсчета и выполнения нужно больше. Алгоритмы очень любят есть память.
Можно создать словарь и для 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),… т.е. входящий символ один и тот же. И детерминировать такую штуку никак нельзя, т.е. мы вынуждены работать недетерминированным автоматом.
Нужно выполнить две операции: композицию преобразователей и поиск кратчайшего пути в результирующем преобразователе.
Сложность композиции: O(V1V2D1(logD2+M2))
V1,V2 — количество состояний первой и второй машины, D1,D2 — максимальное количество исходящих дуг, M2 — мера недерминизма второго трансдьюсера, т.е. максимальное количество дуг, имеющих одинаковую входную метку, и разные исходящие.
Это было бы слишком долго по времени, но есть возможность не проводить полностью композицию сразу, а делать это лениво. Т.е. проводить композицию уже на этапе поиска пути, постепенно «расширяя» трансдьюсер. Таким образом, все элементы в формуле выше будут гораздо меньше. Т.е. только те, по которым мы «проходимся» в результате композиции.
Время поиска кратчайшей строки для тропического полукольца как у алгоритма Дейкстры: O(|E| + |V|log|V|)
— В идеальном варианте, когда ДКА детерминирован, мы получаем линейное время от длины строки. Но тут у нас не-функциональный преобразователь. Т.е. из одной и той же вершины могут выходить (a,a), (a,b), (a,c),… т.е. входящий символ один и тот же. И детерминировать такую штуку никак нельзя, т.е. мы вынуждены работать недетерминированным автоматом.
постепенно расширяя вы можете нарваться на субоптимальный путь типа
пано рама -> панно рама или нано рама, хотя правильно панорама
пано рама -> панно рама или нано рама, хотя правильно панорама
Нет, не могу. Не забывайте, я ищу путь с минимальным весом, при этом веса не могут быть отрицательны. На каждом шаге поиска алгоритм расширяет автомат до границ минимального пути. Т.е. если в конце пути мы нарвемся на большой вес, то вдоль всего пути мы будем расширять ответвления, пока не найдем новый минимальный путь, либо не убедимся, что данный путь и есть минимальный.
Но тут кроется недостаток. При определенных ситуациях расширению могут подвергнуться множество путей, и это сильно затормозит поиск. По этому важно смещать веса в сторону начального состояния автомата. Тогда вычисление будет проходить быстрее. В openfst есть соответствующие для этого методы.
А вообще, хороший вопрос, правильный.
Но тут кроется недостаток. При определенных ситуациях расширению могут подвергнуться множество путей, и это сильно затормозит поиск. По этому важно смещать веса в сторону начального состояния автомата. Тогда вычисление будет проходить быстрее. В openfst есть соответствующие для этого методы.
А вообще, хороший вопрос, правильный.
Ну и в чем тогда оптимизация? Что бы убедиться что данный путь минимальный на полном графе все равно придется сделать полный проход по Дейкстре и следовательно будет сложность больше чем у растояния Левенштейна, навскидку имхо.
Хотя величины там небольшие — надо бы считать сложность с младшими членами и константой…
Хотя величины там небольшие — надо бы считать сложность с младшими членами и константой…
Оптимизация по сравнению с чем? Я не заявляю, что изобрел более эффективный способ расчета расстояния Левенштейна. Я использую то же самое динамическое программирование, просто взгляд с другой стороны. И по сложности оно должно быть ровно таким же.
Определенная оптимизация по сравнению с полным перебором словаря может быть в том, что я упаковываю этот словарь, делаю минимальным. Хотя тоже самое можно сделать и классическими методами (Витерби, если не ошибаюсь).
Кроме того, результирующий автомат раздувается только в худшем случае. И это «раздутие» можно ограничить. К примеру, задав определенное количество возможных ошибок в автомате E.
Вспомните о моей задаче. Преимущество в том, что я работаю с автоматами, и это просто. Это позволяет совместить разные модели воедино. Традиционный подход в лингвистике: отобрать вероятные гипотезы на уровне морфологии, отобрать наиболее вероятные гипотезы на уровне синтаксиса, попробовать вытащить гипотезы используя спелчекер. Каждый уровень — отдельная программа со своим алгоритмом. Здесь же можно слить все вместе, и получить готовый спелчекер, распознаватель голоса, распознаватель паттернов. При этом каждая из гипотез будет рассматриваться на всем пути обработки, и более того, реализовать это — просто.
Кстати, этот придумал не я, вот линк. Там есть и формальные оценки сложности для разных алгебраических структур.
Определенная оптимизация по сравнению с полным перебором словаря может быть в том, что я упаковываю этот словарь, делаю минимальным. Хотя тоже самое можно сделать и классическими методами (Витерби, если не ошибаюсь).
Кроме того, результирующий автомат раздувается только в худшем случае. И это «раздутие» можно ограничить. К примеру, задав определенное количество возможных ошибок в автомате 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 тысяч переходов.
fasten your seatbelts -> faster your seat belts
Sign up to leave a comment.
Penisland, или как написать спеллчекер