Метка «trie»

Игра Wordament — реализация помощника на языке HaskellКак обычно с опозданием в месяц или даже полтора я публикую отчёт о проведённом в начале августа конкурсе по функциональному программированию под эгидой Фонда Поддержки Функционального Программирования ФП(ФП). Задачей конкурса было разработать программное решение для игры Wordament, которая заключается в поиске на квадратном поле 4х4 из букв запрятанных в нём слов. Слова могут быть в любой форме, каждая буква может быть использована в слове только один раз. Переходить от буквы к букве можно по горизонтали, вертикали или диагонали, поэтому иногда слова запрятаны в поле очень мудрёным способом.

Задача осложнялась тем, что один раунд игры длится ровно две минуты, а потому необходимо было реализовать очень быстрое решение — загрузка словаря в память, ввод исходных данных, поиск слов и вывод найденных слов на экран в порядке, отсортированном по возрастанию стоимости слов — всё это надо было сделать очень быстро, чтобы у игрока оставалось время на ввод слов в игру для получения большого количества очков. Скажем, что на экране слова должны были появиться не позднее, чем через 15 секунд после ввода исходных данных.

В конкурсе приняли участие четыре человека, которые написали свои решения на следующих языках программирования: Clojure, Nemerle, Python и Haskell. На основе последнего решения и написана данная краткая заметка.

Так что ежели кто интересуется алгоритмом поиска слов в поле, то добро пожаловать под кат.

Читать полностью »

В далеком 2009 году на хабре уже была статья "Кузявые ли бутявки.." про pymorphy — морфологический анализатор для русского языка на Python (штуковину, которая умеет склонять слова, сообщать информацию о части речи, падеже и т.д.)

В 2012м я начал потихоньку делать pymorphy2 (github, bitbucket) — думаю, самое время представить эту библиотеку тут: pymorphy2 может работать в сотни раз быстрее, чем pymorphy (втч без использования C/C++ расширений) и при этом требовать меньше памяти; там лучше словари, лучше качество разбора, лучше поддержка буквы ё, проще установка и более «честный» API. Из негатива — не все возможности pymorphy сейчас реализованы в pymorphy2.

Эта статья о том, как pymorphy2 создавался (иногда с довольно скучными техническими подробностями), и сколько глупостей я при этом наделал; если хочется просто все попробовать, то можно почитать документацию.

Читать полностью »

Сжатые префиксные деревья Тема префиксных деревьев поиска уже неколько раз поднималась на хабре. Здесь, например, кратко описывается, что такое префиксное дерево и зачем оно нужно, и рассматриваются основные операции над такими деревьями (поиск, вставка, удаление). К сожалению, ничего при этом не говорится про реализацию. В этом недавнем посте рассматривается «питонья библиотека datrie», являющаяся Cython-оберткой библиотеки libdatrie. По последней ссылке имеется хорошее описание реализации частично сжатых префиксных деревьев в виде детерминированных конечных автоматов (с использованием массивов). Я решил внести свои пять копеек в эту тему, рассмотрев реализацию на языке С++ префиксных деревьев с помощью указателей. Кроме того, была и еще одна цель — сравнить между собой поиск строк с помощью сбалансированного двоичного дерева поиска (АВЛ-дерево) и сжатого префиксного дерева.

Читать полностью »

Доделал на днях питонью библиотеку datrie, реализующую префиксное дерево (см. википедию или хабр), спешу поделиться.

Если вкратце, то можно считать, что datrie.Trie — это замена стандартному питоньему dict, которая при определенных условиях (ключи — строки) занимает меньше памяти, имеет сравнимую скорость получения отдельного элемента и поддерживает дополнительные операции (получение всех префиксов данной строки, получение всех строк, начинающихся с данной строки и др.), которые работают примерно так же быстро, как и «словарные» операции.

Работает под Python 2.6-3.3, поддерживает юникод, лицензия LGPL.

Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js