Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 22
За статью спасибо!
Вопросы:
1) доступен ли код?
2) при чем тут C++?
Вопросы:
1) доступен ли код?
2) при чем тут C++?
1) если кому-то интересен код, могу его добавить
2) ну некоторые вставки на плюсах же, и опять же вдруг таки код добавлю (а он на С++)
2) ну некоторые вставки на плюсах же, и опять же вдруг таки код добавлю (а он на С++)
1) Github, bitbucket — конечно добавляйте!
2) Ну все, что в статье, выглядит как код С. Тот же NULL, например.
2) Ну все, что в статье, выглядит как код С. Тот же NULL, например.
Если я вас правильно понял, вы ошиблись: не в узле хранится буква слова, а в ребре дерева; узлу соответствует строка, которую можно восстановить, возвращаясь вверх по дереву. На сколько я помню, такое дерево называется бором, или префиксным деревом.
Можно radix tree сделать (всмысле объединить узлы с одним чайлдом) — будет меньше места есть.
Не факт — в словаре из слов русского языка узлов с одним чайлдом не так много. При этом, чтоб узлы объединять, нужно объединенные строки хранить. Т.е. видимо, это дополнительный указатель + байт-другой для длины на каждый узел.
Radix tree может память сэкономить, когда строк немного, или когда они длинные.
Radix tree может память сэкономить, когда строк немного, или когда они длинные.
А у меня как минимум для первого дерева из статьи (если я всё правильно понял и не накосячил с тупой реализацией) получилось что одиночных чайлдов в районе 67% (такой код и такой словарь). Для префиксного возможно чуть похуже будет.
А где же сами приложения? Интересует Android версия.
Понятно, что пройти путь самостоятельно интересно, но существуют уже готовые продвинутые решения.
Описанное в топике — это нечто похожее на конечный автомат. А вот, превратив его в конечный детерминированный автомат, можно получить предельно эффективное решение. Конечный детерминированный автомат используется во многих лингвистических продуктах: морфология, проверка орфографии, словари и пр. Различных реализаций детерминированного конечного автомата огромное множество на любых языках. Самое сложная часть — это «построитель» такого автомата (существует несколько алгоритмов), а та часть, которая использует уже готовый автомат, вообще состоит из 2 страниц кода, которую можно реализовать на любом языке за минимальное время.
Для примера, файл детерминированного конечного автомата, который состоит из 5 млн. русских слов (для использования проверки орфографии), занимает, как бы это было не удивительно, всего 2 МБ. Автомат можно загружать в память целиком, а можно «мэпить» в памяти. Второй случай идеально подходит для устройств с быстрым доступом к системе хранение (флеш память, например, телефоны и смартфоны) — он практически не требователен к ресурсам, а скорость для пользователя остаётся очень высокой. Это особенно актуально, когда нужно подключать несколько автоматов сразу (например, несколько языков).
Описанное в топике — это нечто похожее на конечный автомат. А вот, превратив его в конечный детерминированный автомат, можно получить предельно эффективное решение. Конечный детерминированный автомат используется во многих лингвистических продуктах: морфология, проверка орфографии, словари и пр. Различных реализаций детерминированного конечного автомата огромное множество на любых языках. Самое сложная часть — это «построитель» такого автомата (существует несколько алгоритмов), а та часть, которая использует уже готовый автомат, вообще состоит из 2 страниц кода, которую можно реализовать на любом языке за минимальное время.
Для примера, файл детерминированного конечного автомата, который состоит из 5 млн. русских слов (для использования проверки орфографии), занимает, как бы это было не удивительно, всего 2 МБ. Автомат можно загружать в память целиком, а можно «мэпить» в памяти. Второй случай идеально подходит для устройств с быстрым доступом к системе хранение (флеш память, например, телефоны и смартфоны) — он практически не требователен к ресурсам, а скорость для пользователя остаётся очень высокой. Это особенно актуально, когда нужно подключать несколько автоматов сразу (например, несколько языков).
А как вы предлагаете решать эту задачу с помощью DFA?
Так решение фактически ничем не отличается от того, что предложил автор, только основа более продвинутая. Автомат состоит из слов, каждая буква — это переход между состояниями. Для работы с автоматом используется лишь одна базовая функция — поиск слов по шаблону со спецсимволом, например, "*". Т.е. на входе подаётся что-то типа "*п*ар***ур", а на выходе получаем все состояния автомата (слова), которые удовлетворяют этому шаблону.
Интересно, когда человек проходит какую-то нетривиальную алгоритмическую задачу от начала и до конца.
Несколько лет назад тоже писал аналогичную программу, потому что надо было решать N на N, а найденные решения работали только в поле 5 на 5. Но у меня был совсем топорный и медленный алгоритм. С Вашим по скорости не сравнить! Но с поставленной задачей справлялся великолепно.
Я помню самое сложное было найти словарь именно существительных. Откуда у Вас словарь на 110 000 слов? И есть ли где-нибудь в открытом доступе специальные коллекции словарей?
Я помню самое сложное было найти словарь именно существительных. Откуда у Вас словарь на 110 000 слов? И есть ли где-нибудь в открытом доступе специальные коллекции словарей?
Мне кажется логичным искать в AppStore по запросу «Балда»(буквально пару недель назад как раз искал решатель для айфона), но я не нахожу потому что у Вас в заголовке "… балды". Точнее нахожу Ваших конкурентов.
Может быть Вы теряете часть аудитории такой же как и я.
Может быть Вы теряете часть аудитории такой же как и я.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм быстрого поиска слов в игре балда