Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 40
Ужас, бросайте это дело — вы знаете русский еще хуже меня, а я его не знаю, но догадываюсь, что:
МЫТЬ — никак не может быть прошедшим временем(скорее будущим), не имеет ни числа ни рода(подозреваю это справедливо для всех глаголов в будущем продолженном времени, ибо он\она\они будут «делать»), про изъявительное наклонение тоже не ясно без вспомогательных слов…
А вообще вся таблица полный бред…
МЫТЬ — никак не может быть прошедшим временем(скорее будущим), не имеет ни числа ни рода(подозреваю это справедливо для всех глаголов в будущем продолженном времени, ибо он\она\они будут «делать»), про изъявительное наклонение тоже не ясно без вспомогательных слов…
А вообще вся таблица полный бред…
Спасибо.
Кстати, под трансдюсерами разные люди понимают разные вещи. Ты, если я правильно понимаю, говоришь по weighted FST. А вот разработчики GATE трансдюсером называют обычный КА, с финальным состоянием которого ассоциированы некие действия.
Кстати, под трансдюсерами разные люди понимают разные вещи. Ты, если я правильно понимаю, говоришь по weighted FST. А вот разработчики GATE трансдюсером называют обычный КА, с финальным состоянием которого ассоциированы некие действия.
Кажется, что дело в деталях. В случае GATE используется обычная минимизация ДКА с некоторыми тонкостями для представления групп.
Для weighted на первый взгляд нужны совершенно другие алгоритмы.
Про эквивалентность — ну вот подход ЭТАПа — построение классического трансдюсера, но если сделать из него КА, который на конечном состоянии выдаст нормальную форму, то он будет сильно большего размера.
И с трансдюсерами кажется отдельная задача — детерминирование по входному/выходному символу.
Просто к чему я это все. У меня на гитхабе там рядом выдрана из GATE работа с общим КА(удаление эпсилон-переходов, НКА -> ДКА, минимизация ДКА). Но для трансдюсеров, тем более с весами, нужны другие алгоритмы.
Для weighted на первый взгляд нужны совершенно другие алгоритмы.
Про эквивалентность — ну вот подход ЭТАПа — построение классического трансдюсера, но если сделать из него КА, который на конечном состоянии выдаст нормальную форму, то он будет сильно большего размера.
И с трансдюсерами кажется отдельная задача — детерминирование по входному/выходному символу.
Просто к чему я это все. У меня на гитхабе там рядом выдрана из GATE работа с общим КА(удаление эпсилон-переходов, НКА -> ДКА, минимизация ДКА). Но для трансдюсеров, тем более с весами, нужны другие алгоритмы.
Для трансдьюсера не существует способа минимизации. То есть минимизировать можно, но автомат в результате не будет гарантированно минимальным (и единственно возможным). Чтобы детерминировать трансдьюсер, нужно чтоб выполнялось свойство проективности, а это на практике редкость (на моей, по крайней мере). Но есть разные обходные пути, типа воспринимать пару символов a:b как оду метку, минимизировать как обычный акцептор.
А чем вам OpenFST не нравится? Ребята хорошо потрудились. Правда, в погоне за универсальностью вышло тяжеловесно. Но вцелом, работает.
А чем вам OpenFST не нравится? Ребята хорошо потрудились. Правда, в погоне за универсальностью вышло тяжеловесно. Но вцелом, работает.
Согласен. Иногда лучше вообще не минимизировать :). Вообще, там есть такая штука, как ленивая композиция. Очень эффективная, когда приходится строить композицию больших автоматов, а потом искать кратчайший путь. Но ее тяжеловато использовать — функция не вынесена в шелл-скрипты, и документации мало.
Складывается ощущение, что все описанное имеет отношение только к морфологии.
Но ведь очевидным желанием является хранить внутри представлений слов как минимум синтаксические свойства слов (ок, на следующем этапе и т. д.) Ведь в конце концов ваш пример с «мама мыла раму» — он про синтаксис. В конечном итоге задача сведется к ответу на вопрос «мыла» — это «мыло» или «мыть». Да и ссылки на примеры систем автоматической обработки текстов — они как минимум не про чистую морфологию.
Соответственно, у переходов в дереве состояний должны быть какие-то веса/вероятности/etc, сигнализирующие морфологические изменения в зависимости от синтаксической роли. Ну или как-то еще структура должна позволять (в будущем) хранить эту (а возможно и другие типы) информации о словах.
Получается, что весь разговор про оптимизацию структур нужно вести в контексте возможности масштабирования и возможности «навески» дополнительных аспектов. Иначе может получиться, что оптимизированное представление, рассчитанное только на морфологическую информацию, не позволит использовать словарь для более-менее реальных прикладных задач.
Ну или по крайней мере хочется понять, зачем нужен словарь, которые содержит только морфологические данные.
Но ведь очевидным желанием является хранить внутри представлений слов как минимум синтаксические свойства слов (ок, на следующем этапе и т. д.) Ведь в конце концов ваш пример с «мама мыла раму» — он про синтаксис. В конечном итоге задача сведется к ответу на вопрос «мыла» — это «мыло» или «мыть». Да и ссылки на примеры систем автоматической обработки текстов — они как минимум не про чистую морфологию.
Соответственно, у переходов в дереве состояний должны быть какие-то веса/вероятности/etc, сигнализирующие морфологические изменения в зависимости от синтаксической роли. Ну или как-то еще структура должна позволять (в будущем) хранить эту (а возможно и другие типы) информации о словах.
Получается, что весь разговор про оптимизацию структур нужно вести в контексте возможности масштабирования и возможности «навески» дополнительных аспектов. Иначе может получиться, что оптимизированное представление, рассчитанное только на морфологическую информацию, не позволит использовать словарь для более-менее реальных прикладных задач.
Ну или по крайней мере хочется понять, зачем нужен словарь, которые содержит только морфологические данные.
Да, все правильно. Пост про представление данных для фактически первого шага анализа. Это даже не описание полного морфологического анализа, поскольку там есть свои особенности.
Обычно анализ текста выглядит примерно так: токенизация, морфологический анализ, [другие стадии анализа].
Вот эти другие стадии анализа бывают очень разными. Следующая классическая стадия — синтаксический анализ. Но он очень ресурсоемкий как с точки зрения построения системы, так и с точки зрения ресурсов для анализа. Во многих случаях достаточно поверхностного анализа на основе списков слов — газетиров. Это фактически тот же морфологический словарь, но другого назначения. Например это — личные имена, фамилии, названия городов, улиц, железнодорожных станций, станций метро. Эти списки тоже надо как-то компактно представлять. А для более-менее приемлемого качества выделения такого рода объектов достаточно простых шаблонных правил вида: [Имя] [Фамилия] или [Фамилия] [Имя] [Отчество]. Эти правила — фактически регулярные выражения, только не над символами строки, а над словами текста. Этот подход используется, например в GATE и позволяет достаточно хорошо выделять объекты.
Мне хотелось написать пост по одной конкретной теме. Например, есть совершенно другая тема — разрешение частеречной омонимии — POS Tagging, на котором обычно и выбирается одна из альтернативных форм слова. (Но, например, в системе ЭТАП-3 другой принцип — там омонимия разрешается одновременно с синтаксическим анализом).
Обычно анализ текста выглядит примерно так: токенизация, морфологический анализ, [другие стадии анализа].
Вот эти другие стадии анализа бывают очень разными. Следующая классическая стадия — синтаксический анализ. Но он очень ресурсоемкий как с точки зрения построения системы, так и с точки зрения ресурсов для анализа. Во многих случаях достаточно поверхностного анализа на основе списков слов — газетиров. Это фактически тот же морфологический словарь, но другого назначения. Например это — личные имена, фамилии, названия городов, улиц, железнодорожных станций, станций метро. Эти списки тоже надо как-то компактно представлять. А для более-менее приемлемого качества выделения такого рода объектов достаточно простых шаблонных правил вида: [Имя] [Фамилия] или [Фамилия] [Имя] [Отчество]. Эти правила — фактически регулярные выражения, только не над символами строки, а над словами текста. Этот подход используется, например в GATE и позволяет достаточно хорошо выделять объекты.
Мне хотелось написать пост по одной конкретной теме. Например, есть совершенно другая тема — разрешение частеречной омонимии — POS Tagging, на котором обычно и выбирается одна из альтернативных форм слова. (Но, например, в системе ЭТАП-3 другой принцип — там омонимия разрешается одновременно с синтаксическим анализом).
А в чем смысл в такой упаковке?
Ну, 5 миллионов словоформ.
Средняя длина русского слова в utf8 если мне не изменяет память 17 байт (могу ошибаться, давно занимался).
Словарь константный, т.е. апдейтов/инсертов/блокировок нет.
Получаем огромное страшное число — 85 мегабайт данных.
Плюс perfect hash (например cmph.sourceforge.net/) — так там несколько бит на запись оверхеда всего.
Ну плюс флаги, падежи, ссылки на нормальные формы.
Как-то не так уж и много.
У меня такие системы на perfect hashes — 10^8 записей и ~700 нс на извлечение записи по ключу занимали, и это еще на компах подревнее нынешних.
Имхо как-то побыстрее префиксных деревьев.
А если размер надо уменьшать, а не время доступа, тогда нужны succinct structures.
Имхо префиксные деревья — не самое лучшее решение.
Ну, 5 миллионов словоформ.
Средняя длина русского слова в utf8 если мне не изменяет память 17 байт (могу ошибаться, давно занимался).
Словарь константный, т.е. апдейтов/инсертов/блокировок нет.
Получаем огромное страшное число — 85 мегабайт данных.
Плюс perfect hash (например cmph.sourceforge.net/) — так там несколько бит на запись оверхеда всего.
Ну плюс флаги, падежи, ссылки на нормальные формы.
Как-то не так уж и много.
У меня такие системы на perfect hashes — 10^8 записей и ~700 нс на извлечение записи по ключу занимали, и это еще на компах подревнее нынешних.
Имхо как-то побыстрее префиксных деревьев.
А если размер надо уменьшать, а не время доступа, тогда нужны succinct structures.
Имхо префиксные деревья — не самое лучшее решение.
Спасибо за ссылку.
Но задача несколько отличается от perfect hash. Надо по строке получать нормальную форму и морфологические характеристики. Это тоже занимает достаточно много места.
Я вот сейчас поставил cmph, прогнал просто список словоформ. Получил, что данные для хеша занимают 21Мб. Время построения — сходное с построением минимального КА. Минимальный КА занимает меньше даже без особой экономии памяти.
Преимущество автомата как раз в том, что его можно менять. В ЭТАПе как раз так и сделано. Есть словарь, который правят лингвисты, он также хранится в виде КА. И КА изменяется на лету без перестроения всего автомата.
Опять же, не было задачи ужать все до минимальных размеров. При желании автомат можно упаковать очень сильно. Например, если переходы изпользовать дельта и varint кодирование для меток переходов. В общем все, что описано в www.aclweb.org/anthology/W/W09/W09-1505.pdf
Но задача несколько отличается от perfect hash. Надо по строке получать нормальную форму и морфологические характеристики. Это тоже занимает достаточно много места.
Я вот сейчас поставил cmph, прогнал просто список словоформ. Получил, что данные для хеша занимают 21Мб. Время построения — сходное с построением минимального КА. Минимальный КА занимает меньше даже без особой экономии памяти.
Преимущество автомата как раз в том, что его можно менять. В ЭТАПе как раз так и сделано. Есть словарь, который правят лингвисты, он также хранится в виде КА. И КА изменяется на лету без перестроения всего автомата.
Опять же, не было задачи ужать все до минимальных размеров. При желании автомат можно упаковать очень сильно. Например, если переходы изпользовать дельта и varint кодирование для меток переходов. В общем все, что описано в www.aclweb.org/anthology/W/W09/W09-1505.pdf
Да, perfect hash константный, за счет чего и скорость запросов обеспечивается.
Я делал обновления оффлайном, с переключением на лету, у меня задача была — высоконагруженный веб-сервис.
Тем более, что на объемах >10^6 изменения очень невелики, иногда за месяц обновлений не набиралось.
Время построения у меня было порядка 2 минут, объем — там смотреть надо, у них от метода хеширования зависит, minimal ordered perfect hash добавляет 32 или 64 бита к каждой записи. Если же он не упорядоченный, то там реально очень небольшие размеры, плюс они хранят их в компрессированном виде.
Морфологическая информация и нормальная форма (точнее то, что у меня было их аналогом) хранилась в массиве, смещение в котором и возвращал хеш (как ID).
Для задачи где много вставок или изменений конечно такой метод неприменим.
А вот там, где база практически не меняется, размеры большие (billions records как пишут авторы) и скорость анализа текста критична — там что доктор прописал.
Я быстрее пока не встречал (из того что сам лично щупал, понятно).
Сейчас вот WordNet думаю туда перегнать.
В общем рекомендую, хорошая либа, хотя со своими тараканами.
Например в случае дубликатов она тупо крешится при построении хеша.
Ну и там еще по мелочи — поведение не всегда очевидное.
Я делал обновления оффлайном, с переключением на лету, у меня задача была — высоконагруженный веб-сервис.
Тем более, что на объемах >10^6 изменения очень невелики, иногда за месяц обновлений не набиралось.
Время построения у меня было порядка 2 минут, объем — там смотреть надо, у них от метода хеширования зависит, minimal ordered perfect hash добавляет 32 или 64 бита к каждой записи. Если же он не упорядоченный, то там реально очень небольшие размеры, плюс они хранят их в компрессированном виде.
Морфологическая информация и нормальная форма (точнее то, что у меня было их аналогом) хранилась в массиве, смещение в котором и возвращал хеш (как ID).
Для задачи где много вставок или изменений конечно такой метод неприменим.
А вот там, где база практически не меняется, размеры большие (billions records как пишут авторы) и скорость анализа текста критична — там что доктор прописал.
Я быстрее пока не встречал (из того что сам лично щупал, понятно).
Сейчас вот WordNet думаю туда перегнать.
В общем рекомендую, хорошая либа, хотя со своими тараканами.
Например в случае дубликатов она тупо крешится при построении хеша.
Ну и там еще по мелочи — поведение не всегда очевидное.
Ага, мне тоже так говорили, что он ломается на определенных размерах.
И приводили примеры — реально ломающиеся, раз так пять показывали и тыкали мордой.
И я во всех пяти случаях смотрел данные и находил дубликаты, он же гарантированно ломается при построении, если данные дублируется. Это у него фича такая.
:-)
Ну и тормознутость perfect hash по сравнению с обычным — это как раз странно (конечно если это не gperf).
На запросах cmph быстрее, я еще делал анализ когда он был 1-й версии, сравнивал его даже с такой прикольной экзотикой как uthash — на макросах который.
По запросам cmph был лидером — там только надо правильный тип выбрать (у меня BDZ по дефолту стоял), у разных типов скорость доступа разная.
На построении там да, разные скорости бывают, но для таких баз данные перестраиваются крайне редко.
Одно дело на десктопе у лингвистов, другое дело — на ядре сервиса.
Правда на 32 битах ни разу не гонял, хз, может там действительно есть проблемы, врать не буду.
И приводили примеры — реально ломающиеся, раз так пять показывали и тыкали мордой.
И я во всех пяти случаях смотрел данные и находил дубликаты, он же гарантированно ломается при построении, если данные дублируется. Это у него фича такая.
:-)
Ну и тормознутость perfect hash по сравнению с обычным — это как раз странно (конечно если это не gperf).
На запросах cmph быстрее, я еще делал анализ когда он был 1-й версии, сравнивал его даже с такой прикольной экзотикой как uthash — на макросах который.
По запросам cmph был лидером — там только надо правильный тип выбрать (у меня BDZ по дефолту стоял), у разных типов скорость доступа разная.
На построении там да, разные скорости бывают, но для таких баз данные перестраиваются крайне редко.
Одно дело на десктопе у лингвистов, другое дело — на ядре сервиса.
Правда на 32 битах ни разу не гонял, хз, может там действительно есть проблемы, врать не буду.
Сейчас проверил, на второй версии вроде не падает по дубликатам, возвращает ошибку.
В первой версии крешился, что было неудобно и заставляло заказчика нервничать. :-)
У них в доке было, что при некоторых seed создание хеша может быть неудачным, но вероятность такого события тем меньше, чем больше записей.
Сам ни разу не попадал чтобы падало без дубликатов, но и так чтобы меньше 10^5 никогда не строил — даже на тестах, но и там не падало. Поэтому и удивился, что на миллионах упало.
У меня было так — словарь слов ~20М, короткие слова 3-20 символов, но utf8, по байтам не помню статистику, но большинство символов ASCII.
Дополнительный словарь — пары индексов (т.е. 4+4=8 байт) — ~80М.
И был словарь пар слов вспомогательный (редко используемый), где-то 120М, там длинные комбинации, потом убрал его, но основные замеры на нем делал.
Меня память не лимитировала никак, серваки начинались от 32Г, а вот скорость была крайне критична, поэтому я тупо хранил строки в массиве не заморачиваясь, быстрее индексного доступа все равно ничего не бывает.
Предобработка у CMPH конечно медленная, тут даже не спорю, это тот еще тормоз.
По скорости доступа там на самом деле получается вот что.
Это хеш возвращает номер от 0 до N-1 для любой строки, даже если ее в хеше нет.
Поэтому потом надо еще делать прямое сравнение, что тоже какое-то время забирает, сама либа этого не делает, она сильно уж низкоуровневая.
Это в принципе похоже на то, что происходит в обычном хеше, но в обычном хеше в случае коллизии надо делать несколько таких сравнений, а здесь только одно единственное и гарантировано единственное. С другой стороны хеш-функция в обычном хеше сильно проще будет и в этой точке как раз может быть сравнение не в пользу cmph.
Хе, я даже сначала (до замеров скорости) Bloom Filter соорудил для предварительной фильтрации — однако оказалось что никакого реального профита он не дает, быстрее получить индекс и сравнить строку напрямую.
Кроме того по статистике запросов увидел, что большинство запросов были в хеше, так что и надобность отпала даже концептуально.
В принципе можно оттюнить и проверить с каким-нибудь обычным hash_map, тоже тюнированным.
Я еще с первой версией все измерения делал, вторую уже давно механически использую в коде без анализа.
На продакшене несколько лет работает, не падает, нареканий нет.
PS
Я не лингвист, это халтурка была, но такие халтурки возникают достаточно регулярно.
В первой версии крешился, что было неудобно и заставляло заказчика нервничать. :-)
У них в доке было, что при некоторых seed создание хеша может быть неудачным, но вероятность такого события тем меньше, чем больше записей.
Why do I always get the error «Unable to create minimum perfect hashing function»?
— The algorithms do not guarantee that a minimal perfect hash function can be created. In practice, it will always work if your input is big enough (>100 keys). The error is probably because you have duplicated keys in the input. You must guarantee that the keys are unique in the input.
Сам ни разу не попадал чтобы падало без дубликатов, но и так чтобы меньше 10^5 никогда не строил — даже на тестах, но и там не падало. Поэтому и удивился, что на миллионах упало.
У меня было так — словарь слов ~20М, короткие слова 3-20 символов, но utf8, по байтам не помню статистику, но большинство символов ASCII.
Дополнительный словарь — пары индексов (т.е. 4+4=8 байт) — ~80М.
И был словарь пар слов вспомогательный (редко используемый), где-то 120М, там длинные комбинации, потом убрал его, но основные замеры на нем делал.
Меня память не лимитировала никак, серваки начинались от 32Г, а вот скорость была крайне критична, поэтому я тупо хранил строки в массиве не заморачиваясь, быстрее индексного доступа все равно ничего не бывает.
Предобработка у CMPH конечно медленная, тут даже не спорю, это тот еще тормоз.
По скорости доступа там на самом деле получается вот что.
Это хеш возвращает номер от 0 до N-1 для любой строки, даже если ее в хеше нет.
Поэтому потом надо еще делать прямое сравнение, что тоже какое-то время забирает, сама либа этого не делает, она сильно уж низкоуровневая.
Это в принципе похоже на то, что происходит в обычном хеше, но в обычном хеше в случае коллизии надо делать несколько таких сравнений, а здесь только одно единственное и гарантировано единственное. С другой стороны хеш-функция в обычном хеше сильно проще будет и в этой точке как раз может быть сравнение не в пользу cmph.
Хе, я даже сначала (до замеров скорости) Bloom Filter соорудил для предварительной фильтрации — однако оказалось что никакого реального профита он не дает, быстрее получить индекс и сравнить строку напрямую.
Кроме того по статистике запросов увидел, что большинство запросов были в хеше, так что и надобность отпала даже концептуально.
В принципе можно оттюнить и проверить с каким-нибудь обычным hash_map, тоже тюнированным.
Я еще с первой версией все измерения делал, вторую уже давно механически использую в коде без анализа.
На продакшене несколько лет работает, не падает, нареканий нет.
PS
Я не лингвист, это халтурка была, но такие халтурки возникают достаточно регулярно.
Достаточно интересно будет посмотреть на результаты, тем более что я например с Boost не сравнивал, на том заказе Boost был не в фаворе, потому я время тогда сэкономил.
Я вот думаю скорость доступа в зависимости от размера хеша как-нибудь посчитать, задержка там растет сублинейно, но заметно.
Ну и для каждого типа хеша задержка очень разная.
Я нашел старую табличку по скорости именно cmph, осталась в старых доках.
Процессор правда неизвестен и по другим хешам данных нет.
Похоже на домашней машине гонял, но на которой — уже не вспомнить.
10М 40-байтовых рандомных ключей, т.е. ключи достаточно длинные, на коротких понятно может быть сильно другая картина.
Измерялось время 1М чтений и размер хеша (без самих строк).
Вот что получилось
BDZ
размер 3 459 422 байт
время 809 мс
BMZ
размер 46 000 052 байт
время 656 мс
CHM (ordered)
размер 83 600 052 байт
время 727 мс
CHD
размер 5 293 580 байт
время 1288 мс
Все остальные настройки были по дефолту.
Ну и это первая версия cmph была, может даже еще 0.9.
Но это время вместе со сравнением строки, это не только вычисление самой функции.
Я вот думаю скорость доступа в зависимости от размера хеша как-нибудь посчитать, задержка там растет сублинейно, но заметно.
Ну и для каждого типа хеша задержка очень разная.
Я нашел старую табличку по скорости именно cmph, осталась в старых доках.
Процессор правда неизвестен и по другим хешам данных нет.
Похоже на домашней машине гонял, но на которой — уже не вспомнить.
10М 40-байтовых рандомных ключей, т.е. ключи достаточно длинные, на коротких понятно может быть сильно другая картина.
Измерялось время 1М чтений и размер хеша (без самих строк).
Вот что получилось
BDZ
размер 3 459 422 байт
время 809 мс
BMZ
размер 46 000 052 байт
время 656 мс
CHM (ordered)
размер 83 600 052 байт
время 727 мс
CHD
размер 5 293 580 байт
время 1288 мс
Все остальные настройки были по дефолту.
Ну и это первая версия cmph была, может даже еще 0.9.
Но это время вместе со сравнением строки, это не только вычисление самой функции.
Если правильно понял статью и комментарий, то штука, похожая на «дельта кодирование переходов», есть в реализации DAFSA code.google.com/p/dawgdic/. Конкретно в dawgdic есть ограничение на общее количество переходов (из-за 32битных чисел везде), так что гугл-н-граммы туда засунуть не получится. Но для морфологии работает отлично.
Скорее всего, судя по внушительному списку литературы там.
Но странно, что там реализован только алгоритм для отсортированных строк. В основной статье как раз два алгоритма: для отсоритрованных и нет.
Я реализовывал алгоритм, который работает без предварительной сортировки входных данных.
Но странно, что там реализован только алгоритм для отсортированных строк. В основной статье как раз два алгоритма: для отсоритрованных и нет.
Я реализовывал алгоритм, который работает без предварительной сортировки входных данных.
Похоже, сортировка требуется как раз из-за способа кодирования автомата: он хранится одним куском памяти, без указателей («double array»), и поэтому удаление оттуда требует перемещения большого количества данных. Видимо, с упорядоченными входными данными можно инкрементально строить автомат без необходимости удалять оттуда что-либо — или хотя бы локализовать изменения, сообразить сейчас не могу.
Большинство систем морфологии создавались в бородатые времена, когда память имела больше значения. При этом скорость морфологического анализа для многих реальных задач узким местом не является: особого смысла во всех этих миллионах разборов/сек нет, когда большинство алгоритмов синтаксического анализа — O(N^3) от длины предложения. Мне кажется, из-за этого такая любовь к префиксным деревьям.
Насчет размера: насколько знаю, способа закодировать DAFSA (иногда aka DAWG) как «succinct data structure» пока не придумали (с сохранением хотя бы асимптотики всех операций), а для задач морфологии получается, что DAFSA занимает меньше памяти, чем всяческие succinct trie, так что уменьшить размер не получается.
Ну и еще в деревьях/DAFSA можно разные операции делать хитрые, в духе «пройтись по дереву, считая переходы е и ё равноценными» или «найти все возможные разборы слова», или «найти все возможные разборы слова, оканчивающегося на данную строку», они очень просто там реализуются. В случае с хэшем для каждого слова нужно ведь списки возможных разборов хранить, их ведь несколько?
Использование хэшей немного смещает баланс «скорость <-> память» в сторону скорости (особенно если не нужны «хитрые» операции). Получается выигрыш раз в 10 по памяти и проигрыш раза в 2-4 по скорости. Но скорости и так хватает за глаза (у меня выходило в среднем 1500ns для получения всех разборов слова из DAFSA, с учетом обертки на Python), а реализации и там, и там достаточно простые, особенно если готовые библиотеки использовать. Видимо, поэтому DAFSA используют чаще.
Насчет размера: насколько знаю, способа закодировать DAFSA (иногда aka DAWG) как «succinct data structure» пока не придумали (с сохранением хотя бы асимптотики всех операций), а для задач морфологии получается, что DAFSA занимает меньше памяти, чем всяческие succinct trie, так что уменьшить размер не получается.
Ну и еще в деревьях/DAFSA можно разные операции делать хитрые, в духе «пройтись по дереву, считая переходы е и ё равноценными» или «найти все возможные разборы слова», или «найти все возможные разборы слова, оканчивающегося на данную строку», они очень просто там реализуются. В случае с хэшем для каждого слова нужно ведь списки возможных разборов хранить, их ведь несколько?
Использование хэшей немного смещает баланс «скорость <-> память» в сторону скорости (особенно если не нужны «хитрые» операции). Получается выигрыш раз в 10 по памяти и проигрыш раза в 2-4 по скорости. Но скорости и так хватает за глаза (у меня выходило в среднем 1500ns для получения всех разборов слова из DAFSA, с учетом обертки на Python), а реализации и там, и там достаточно простые, особенно если готовые библиотеки использовать. Видимо, поэтому DAFSA используют чаще.
В принципе логично, DAFSA достаточно эффективен и универсален, а perfect hash — это решение одной задачи.
Я просто привык все решать по UNIX way — для поиска одна структура, для допустим экстракции всех n-грамм — другая…
Это на самом деле не всегда хорошо.
В данном случае возможно гибкость более практична, в реальных текстах смешивание е/ё — не самая малая из проблем.
Я просто привык все решать по UNIX way — для поиска одна структура, для допустим экстракции всех n-грамм — другая…
Это на самом деле не всегда хорошо.
В данном случае возможно гибкость более практична, в реальных текстах смешивание е/ё — не самая малая из проблем.
Кстати, скорость важна для индексирования. Но в этом случае нужен не полный анализ, а лемматизация.
Для меня лично смысл в том, что упакованный словарь форм дает приятный такой баланс между размером данных и скоростью работы.
Плюс автомат с суффиксами ловко угадывает леммы для неизвестных слов, с хешами тоже можно, но реализация прикидочно помуторнее.
Плюс автомат с суффиксами ловко угадывает леммы для неизвестных слов, с хешами тоже можно, но реализация прикидочно помуторнее.
Вспомнилась байка про компьютерный анализ текстов Михаила Щербакова. Программа выдала, что самые частотные глаголы у Михаила Константиновича — «мыть» и «какать». Т.к. автор программы не смог припомнить ни одной песни, в которой бы эти глаголы встречались, он провёл тщательный анализ. Выяснилось, что к этим глаголам программа привела словоформы «мой», «моя» и «какая».
А никто случайно не задался целью собрать вместе хотя бы информацию о разработчиках и п.о? тот же морфоанализ, свободные словари… Инфа есть, тот же АОТ, словари синонимов, но всё очень разрознено.
Это все очень сложно. Вообще есть такой проект — nlpub.ru ведет его eveel. Но вот использовать все вместе составляет довольно большие технические трудности. Например, есть открытая морфология АОТ, с другой стороны — есть открытая часть НКРЯ (национального корпуса русского языка) с морфологической разметкой. Казалось бы, взять — и фактически готовый POS-теггер. Но в АОТ приняты одни соглашения, в НКРЯ — другие, в СинТагРусе (корпус с синтаксической разметкой) — третьи. Их частично можно преобразовывать между собой, но во многом требуется преобразование руками.
С другой стороны — многие разработки закрыты, причем как коммерческие, так и академические. И разработчики ими делятся не очень охотно. Это тоже понятно — разработка лингвистических ресурсов трудоемко.
С другой стороны — многие разработки закрыты, причем как коммерческие, так и академические. И разработчики ими делятся не очень охотно. Это тоже понятно — разработка лингвистических ресурсов трудоемко.
Ну так присоединяйтесь к NLPub, будем рады видеть. У нас всё это есть и мы работаем на CC BY-SA :)
Пару лет назад реализовывали Дацюка для неупорядоченной последовательности входящих строк. Есть статья, в ней сравнение mafsa с популярными встраиваемыми реализациями БД sqlite и BerkeleyDB, и с std::map, а также о том, как по-разному можно использовать mafsa даже не в формате трансдюсера. Вы здорово объяснили алгоритм, буду теперь молодым коллегам давать ссылку.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Способы представления словарей для автоматической обработки текстов