Почему так не любят автоматы. Упакованная русская морфология займет несколько мегабайт. Поиск — линейный. Так реализовано, к примеру, на aot.
Конечно, можно использовать и хеши, но предыдущий вариант имеет много своих плюсов (генерация словоформ, предсказание формы слова)
Once upon a midnight dreary, long we pondered weak and weary,
Over many a quaint and curious volume of translation lore.
When our system does translation, lifeless prose is its creation;
Making verse with inspiration no machine has done before.
So we want to boldly go where no machine has gone before.
Отличная вариация на тему Эдгара По. Just translation, nothing more :)
Оптимизация по сравнению с чем? Я не заявляю, что изобрел более эффективный способ расчета расстояния Левенштейна. Я использую то же самое динамическое программирование, просто взгляд с другой стороны. И по сложности оно должно быть ровно таким же.
Определенная оптимизация по сравнению с полным перебором словаря может быть в том, что я упаковываю этот словарь, делаю минимальным. Хотя тоже самое можно сделать и классическими методами (Витерби, если не ошибаюсь).
Кроме того, результирующий автомат раздувается только в худшем случае. И это «раздутие» можно ограничить. К примеру, задав определенное количество возможных ошибок в автомате E.
Вспомните о моей задаче. Преимущество в том, что я работаю с автоматами, и это просто. Это позволяет совместить разные модели воедино. Традиционный подход в лингвистике: отобрать вероятные гипотезы на уровне морфологии, отобрать наиболее вероятные гипотезы на уровне синтаксиса, попробовать вытащить гипотезы используя спелчекер. Каждый уровень — отдельная программа со своим алгоритмом. Здесь же можно слить все вместе, и получить готовый спелчекер, распознаватель голоса, распознаватель паттернов. При этом каждая из гипотез будет рассматриваться на всем пути обработки, и более того, реализовать это — просто.
Кстати, этот придумал не я, вот линк. Там есть и формальные оценки сложности для разных алгебраических структур.
Нет, не могу. Не забывайте, я ищу путь с минимальным весом, при этом веса не могут быть отрицательны. На каждом шаге поиска алгоритм расширяет автомат до границ минимального пути. Т.е. если в конце пути мы нарвемся на большой вес, то вдоль всего пути мы будем расширять ответвления, пока не найдем новый минимальный путь, либо не убедимся, что данный путь и есть минимальный.
Но тут кроется недостаток. При определенных ситуациях расширению могут подвергнуться множество путей, и это сильно затормозит поиск. По этому важно смещать веса в сторону начального состояния автомата. Тогда вычисление будет проходить быстрее. В openfst есть соответствующие для этого методы.
Такие штуки не просто запихнуть в коробочные продукты. И дело даже не в сложности разработки. Просто сложно сделать универсальный чекер: это сильно зависит от задачи. Для корректировки поисковых запросов нужно одно, для исправления по тексту -другое и т.п.
Да, вы правы. Там похожая штука, с тем отличием что там не трансдьюсер, а акцептор. Это позволяет искать слова в словаре за линейное время. А статейка и правда неплохая, там рассказывается как в эту штуку добавить строку, сохраняя детерминированность.
Нужно выполнить две операции: композицию преобразователей и поиск кратчайшего пути в результирующем преобразователе.
Сложность композиции: O(V1V2D1(logD2+M2))
V1,V2 — количество состояний первой и второй машины, D1,D2 — максимальное количество исходящих дуг, M2 — мера недерминизма второго трансдьюсера, т.е. максимальное количество дуг, имеющих одинаковую входную метку, и разные исходящие.
Это было бы слишком долго по времени, но есть возможность не проводить полностью композицию сразу, а делать это лениво. Т.е. проводить композицию уже на этапе поиска пути, постепенно «расширяя» трансдьюсер. Таким образом, все элементы в формуле выше будут гораздо меньше. Т.е. только те, по которым мы «проходимся» в результате композиции.
Время поиска кратчайшей строки для тропического полукольца как у алгоритма Дейкстры: O(|E| + |V|log|V|)
— В идеальном варианте, когда ДКА детерминирован, мы получаем линейное время от длины строки. Но тут у нас не-функциональный преобразователь. Т.е. из одной и той же вершины могут выходить (a,a), (a,b), (a,c),… т.е. входящий символ один и тот же. И детерминировать такую штуку никак нельзя, т.е. мы вынуждены работать недетерминированным автоматом.
Сейчас словарь — 30 000 слов, в скомпилированном виде — 13Мб. Модель языка — что-то около 10Мб, правда о-очень ужатая (в смысле, сознательно пошел на снижение точности для экономии ресурсов).
Можно создать словарь и для 300 000 слов, но ресурсов для обсчета и выполнения нужно больше. Алгоритмы очень любят есть память.
Шутки шутками, но взвешенные автоматы эквиваленты модальной логике второго порядка (MSO-logic). Так что может что-то получится смастерить в этом направлении.
Он не Рассел, он Питер :). Рассел — это другой хороший мужик, кто с ним книжку написал.
Я не тестировал, руки не дошли. Но тестовый набор у меня есть, возможно прогоню тесты. Кстати, вот тут выложены полезные файлы norvig.com/ngrams/. Но тут имеет смысл сравнивать проверку по отдельным словам: тот корректор, что описан у него в статье не обращает внимание на контекст, и работает только с отдельными словами. Я пытаюсь исправить набор слов.
Ну, семантика это отдельная тема, и очень непростая. Разве что тренироваться на wordnet'е, да и то, будет неточно.
Здесь даже синтаксиса и морфологии нет в обычном понимании. Но, хотя, последний довольно просто прикрутить.
По мне преобразование multi pli city -> multiplicity вполне корректно. Но вообще, разница такая возникает из-за различия весов в исправлении ошибки вставки/удаления пробела. Это можно варьировать, меняя веса.
Рад, что понравилось. Относительно вашего вопроса — это не гугл и не яндекс. Работаю в небольшой софтовой конторе. Занимаюсь всем: от программирования до маркетинга. А эта тематика — просто хобби последний трех лет. Но чувствую, что это хобби перерастает во что-то большее.
Алгоритм для создания и прохода по автомату довольно простой. А вот детерминизация и упаковка, действительно, нетривиальные в реализации.
Конечно, можно использовать и хеши, но предыдущий вариант имеет много своих плюсов (генерация словоформ, предсказание формы слова)
Over many a quaint and curious volume of translation lore.
When our system does translation, lifeless prose is its creation;
Making verse with inspiration no machine has done before.
So we want to boldly go where no machine has gone before.
Отличная вариация на тему Эдгара По. Just translation, nothing more :)
Определенная оптимизация по сравнению с полным перебором словаря может быть в том, что я упаковываю этот словарь, делаю минимальным. Хотя тоже самое можно сделать и классическими методами (Витерби, если не ошибаюсь).
Кроме того, результирующий автомат раздувается только в худшем случае. И это «раздутие» можно ограничить. К примеру, задав определенное количество возможных ошибок в автомате E.
Вспомните о моей задаче. Преимущество в том, что я работаю с автоматами, и это просто. Это позволяет совместить разные модели воедино. Традиционный подход в лингвистике: отобрать вероятные гипотезы на уровне морфологии, отобрать наиболее вероятные гипотезы на уровне синтаксиса, попробовать вытащить гипотезы используя спелчекер. Каждый уровень — отдельная программа со своим алгоритмом. Здесь же можно слить все вместе, и получить готовый спелчекер, распознаватель голоса, распознаватель паттернов. При этом каждая из гипотез будет рассматриваться на всем пути обработки, и более того, реализовать это — просто.
Кстати, этот придумал не я, вот линк. Там есть и формальные оценки сложности для разных алгебраических структур.
Но тут кроется недостаток. При определенных ситуациях расширению могут подвергнуться множество путей, и это сильно затормозит поиск. По этому важно смещать веса в сторону начального состояния автомата. Тогда вычисление будет проходить быстрее. В openfst есть соответствующие для этого методы.
А вообще, хороший вопрос, правильный.
Я просто не рассказал это в статье, чтоб не перегружать. Если хотите — вышлю картинку модели ошибок.
Нужно выполнить две операции: композицию преобразователей и поиск кратчайшего пути в результирующем преобразователе.
Сложность композиции: O(V1V2D1(logD2+M2))
V1,V2 — количество состояний первой и второй машины, D1,D2 — максимальное количество исходящих дуг, M2 — мера недерминизма второго трансдьюсера, т.е. максимальное количество дуг, имеющих одинаковую входную метку, и разные исходящие.
Это было бы слишком долго по времени, но есть возможность не проводить полностью композицию сразу, а делать это лениво. Т.е. проводить композицию уже на этапе поиска пути, постепенно «расширяя» трансдьюсер. Таким образом, все элементы в формуле выше будут гораздо меньше. Т.е. только те, по которым мы «проходимся» в результате композиции.
Время поиска кратчайшей строки для тропического полукольца как у алгоритма Дейкстры: O(|E| + |V|log|V|)
— В идеальном варианте, когда ДКА детерминирован, мы получаем линейное время от длины строки. Но тут у нас не-функциональный преобразователь. Т.е. из одной и той же вершины могут выходить (a,a), (a,b), (a,c),… т.е. входящий символ один и тот же. И детерминировать такую штуку никак нельзя, т.е. мы вынуждены работать недетерминированным автоматом.
Можно создать словарь и для 300 000 слов, но ресурсов для обсчета и выполнения нужно больше. Алгоритмы очень любят есть память.
Конечно, тут просто совпало. Он исправил три ошибки, выбрав самую вероятную гипотезу.
Я не тестировал, руки не дошли. Но тестовый набор у меня есть, возможно прогоню тесты. Кстати, вот тут выложены полезные файлы norvig.com/ngrams/. Но тут имеет смысл сравнивать проверку по отдельным словам: тот корректор, что описан у него в статье не обращает внимание на контекст, и работает только с отдельными словами. Я пытаюсь исправить набор слов.
Здесь даже синтаксиса и морфологии нет в обычном понимании. Но, хотя, последний довольно просто прикрутить.