Как стать автором
Обновить

Комментарии 22

За статью спасибо!

Вопросы:
1) доступен ли код?
2) при чем тут C++?
1) если кому-то интересен код, могу его добавить
2) ну некоторые вставки на плюсах же, и опять же вдруг таки код добавлю (а он на С++)
1) Github, bitbucket — конечно добавляйте!
2) Ну все, что в статье, выглядит как код С. Тот же NULL, например.
Если я вас правильно понял, вы ошиблись: не в узле хранится буква слова, а в ребре дерева; узлу соответствует строка, которую можно восстановить, возвращаясь вверх по дереву. На сколько я помню, такое дерево называется бором, или префиксным деревом.
ну естественно физически в узле никакая буква не хранится, я так писал для понятности
Можно radix tree сделать (всмысле объединить узлы с одним чайлдом) — будет меньше места есть.
Не факт — в словаре из слов русского языка узлов с одним чайлдом не так много. При этом, чтоб узлы объединять, нужно объединенные строки хранить. Т.е. видимо, это дополнительный указатель + байт-другой для длины на каждый узел.

Radix tree может память сэкономить, когда строк немного, или когда они длинные.
А у меня как минимум для первого дерева из статьи (если я всё правильно понял и не накосячил с тупой реализацией) получилось что одиночных чайлдов в районе 67% (такой код и такой словарь). Для префиксного возможно чуть похуже будет.
Хотя это не сильно много, да.
А где же сами приложения? Интересует Android версия.
ios-версия в app store называется «помощник для балды», андроид-версия сделана, но никуда не выложена
Планирует выложить?
я бы выложил, но у меня пока нет аккаунта разработчика гугл-плей, как появится — сразу выложу
Понятно, что пройти путь самостоятельно интересно, но существуют уже готовые продвинутые решения.

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

Для примера, файл детерминированного конечного автомата, который состоит из 5 млн. русских слов (для использования проверки орфографии), занимает, как бы это было не удивительно, всего 2 МБ. Автомат можно загружать в память целиком, а можно «мэпить» в памяти. Второй случай идеально подходит для устройств с быстрым доступом к системе хранение (флеш память, например, телефоны и смартфоны) — он практически не требователен к ресурсам, а скорость для пользователя остаётся очень высокой. Это особенно актуально, когда нужно подключать несколько автоматов сразу (например, несколько языков).
А как вы предлагаете решать эту задачу с помощью DFA?
Так решение фактически ничем не отличается от того, что предложил автор, только основа более продвинутая. Автомат состоит из слов, каждая буква — это переход между состояниями. Для работы с автоматом используется лишь одна базовая функция — поиск слов по шаблону со спецсимволом, например, "*". Т.е. на входе подаётся что-то типа "*п*ар***ур", а на выходе получаем все состояния автомата (слова), которые удовлетворяют этому шаблону.
на входе подаётся что-то типа "*п*ар***ур"

не много не понял, откуда берется такой шаблон? Ну т.е. как он формируется?

А вы бы могли реализовать эту задачу на основе таких автоматов, потом сравнили бы скорость поиска с моим алгоритмом (этакий челендж)
Интересно, когда человек проходит какую-то нетривиальную алгоритмическую задачу от начала и до конца.
Несколько лет назад тоже писал аналогичную программу, потому что надо было решать N на N, а найденные решения работали только в поле 5 на 5. Но у меня был совсем топорный и медленный алгоритм. С Вашим по скорости не сравнить! Но с поставленной задачей справлялся великолепно.

Я помню самое сложное было найти словарь именно существительных. Откуда у Вас словарь на 110 000 слов? И есть ли где-нибудь в открытом доступе специальные коллекции словарей?
Откуда у Вас словарь на 110 000 слов?

Я его взял из приложения балды в одной социальной сети, точнее из группы этого приложения.
И есть ли где-нибудь в открытом доступе специальные коллекции словарей?

Вот этого не знаю
Мне кажется логичным искать в AppStore по запросу «Балда»(буквально пару недель назад как раз искал решатель для айфона), но я не нахожу потому что у Вас в заголовке "… балды". Точнее нахожу Ваших конкурентов.
Может быть Вы теряете часть аудитории такой же как и я.
действительно, я и сам это заметил после публикации. Так-то в ключевых словах я указывал именно «балда».
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории