В OpenCorpora.org словари тоже есть ( opencorpora.org/dict.php ) — но количество лемм с aot.ru сравнивать там некорректно, т.к. у OpenCorpora леммы более «гранулированные» + доступна информация о связях между леммами. У aot.ru связанные (по терминологии OpenCorpora) леммы просто объединены в одну. Лучше imho количество словоформ писать.
Еще пилю github.com/kmike/pymorphy2 потихоньку — там основа готова (подготовка словарей из OpenCorpora, разбор слов по словарю, предсказатель, работа с Cython-расширениями и без них — все со скоростью порядка 100тыс слов/сек и потреблением памяти порядка 15Мб) — нужно подописывать еще документацию, выложить скомпиленные словари и релиз сделать, но, мне кажется, в список тоже добавлять можно.
Наследование моделей — это синтаксический сахар к OneToOneField (imho очень редко когда нужный); в базе при наследовании от User данные располагались в разных таблицах. С AUTH_USER_MODEL — в одной таблице (+ обязательных полей вроде меньше).
Тут пока нечего допиливать. Вот добавили новое правило, как проверить, лучше стало разбирать или хуже (precision, recall)? А никак сейчас. Что-то, возможно, лучше стало разбирать, а что-то хуже. Добавили «тью» для числительных, солист Muse стал числительным.
Допиливание в текущем виде не приближает к идеалу (и imho является напрасной тратой времени), т.к. критериев для добавления/изменения/удаления правил нет.
Чтоб были критерии какие-то, нужна какая-то оценка качества разбора. Код нужно поэтому писать для оценки качества разбора (анализатор написали уже), а на основе этих оценок уже выбирать правила (если уж собрались их вручную собирать).
Самое простое — это прогнать словарь русского языка через функцию и посмотреть количество правильных — неправильных — лишних вариантов разбора (вот и выяснится, кого там больше, числительных или существительных с тью, и какое правило правильней добавить будет).
… и мы опять пришли к словарю — не проще-продуктивнее ли тогда написать программу, которая сама правила подберет, чтоб оценка разбора была максимальной, вместо того, чтоб пробовать правила самим?
Множество исключений вполне конечно, и закономерности там есть.
Но подход в статье и правда принципиально неправильный: выдумывать эти закономерности от балды — вместо того, чтобы выявить их из словаря + возможно, какой-то частотной статистики. Тут, в принципе, код анализатора даже имел бы право на жизнь, если б данные не от балды были, а какие-то осмысленные.
Вы сейчас строите предсказатель на основе набора окончаний, а правила подбираете вручную на основании своих предположений и наблюдений.
Со словарем этот же набор правил (окончание => часть речи) можно построить автоматически, более полно и правильно (что и делается в phpmorphy и большинстве других морф. анализаторов для русского языка). Благо словари для русского языка доступные и хорошие: см., например, opencorpora.org/dict.php.
Кроме того, раз уж есть словарь, то необязательно полагаться только на предсказатель — если слово есть в словаре, то можно и точный разбор вернуть (ну с учетом неустранимой на уровне отдельных слов неоднозначности разбора).
В libdatrie Double-Array используется, кстати, именно чтоб экономить память на узлах — в узлах не нужно хранить указатели. У вас там 3 указателя на узел (1 на текст и 2 для связи — это по 12 или 24 байта на узел в зависимости от разрядности ОС). По моим тестам (опять-таки те 3млн слов) Double-Array был эффективнее (по памяти) PAT-trie примерно в 2 раза, несмотря на то, что узлов больше.
Кроме того, хранение всего в линейных массивах должно ускорять работу, т.к. данные префетчатся в кеш процессора (а хождение по указателям для современных процессоров — это кошмар, т.к, нужно брать данные из разных участков памяти и пре-заполнение кеша не работает). По скорости самым быстрым считается HAT-trie, в котором структура данных спроектирована именно исходя из интересов современных процессоров, чтоб данные в кеш процессора попадали (но там гибрид trie и хэш-таблицы получился, и из-за этого всякие trie-операци медленные и корявые).
«Полностью сжатое дерево», которое вы реализовали, вроде бы Patricia Tree называется (еще Radix Trie или PAT-trie).
В libdatrie достаточно большие накладные расходы на поддержку юникода: для каждого символа производится преобразование между «внешним» алфавитом и внутренним, и время поиска зависит линейно от количества интервалов во внешнем алфавите. Т.е. сравнение времени поиска не совсем 1 к 1 (вопрос о полезности этой фичи — отдельный).
К тому же в libdatrie каждому ключу сопоставляется целое число (это +4 байта к каждому ключу), а в вашей реализации нет, поэтому замеры памяти нечестные :)
Префиксные деревья, кстати, довольно плохо текстовую информацию все-таки сжимают. Самая эффективная схема хранения пока, насколько знаю, — это LOUDS-trie (в котором данные упаковываются с помощью разных битовых трюков). Есть MARISA-trie code.google.com/p/marisa-trie/, в котором строки хранятся в LOUDS-trie, а остатки не хранятся «как есть», а помещаются в LOUDS-trie следующего уровня (поэтому «рекурсивное trie») — на моих данных (3млн русских слов в utf8) marisa-trie тратит примерно в 10 раз меньше памяти, чем lidatrie. При этом каждому ключу в MARISA-trie тоже сопоставляется значение (4байтовое целое число), но это число не произвольное, а получается из ключа с использованием perfect hash-функции (которая вычисляет значение на основе положения ключа в дереве) — и поэтому эти значения памяти не требуют совсем.
Но MARISA-trie — это хак, причем я так и не понял, зачем он) Эта схема не поддерживает вставку новых значений и удаление существующих, а раз так, то MARISA-trie становится просто небыстрым не до конца минимизированным DAWG.
В DAWG текстовые данные занимают еще меньше места, т.к. строится минимальный автомат для данных строк. Те же 3 млн русских слов в utf8 в DAWG занимают меньше 3М с учетом значений (в 30+ раз меньше, чем в libdatrie) в реализации code.google.com/p/dawgdic/ — это DAWG, который основан на минимизации Double-Array Trie (той же структуры, что и в libdatrie).
Если интересно, еще обзор различных структур данных делал (применительно к питону, на английском, с уклоном в префиксные деревья): kmike.ru/python-data-structures/
Можно еще добавить scikit-learn.org/ к этому списку — это библиотека, в которой собрано почти все, что нужно для машинного обучения: много разных классификаторов (с хорошей реализацией, все что угодно), подсчет tf-idf, есть cython-реализация HMM (в дев-версии с гитхаба) и т.д.
— причем это не просто покрытие тестами, а 100% branch coverage и 100 MC/DC покрытие, и вообще цифры покрытия тут совсем не главные, их можно было гораздо меньшими усилиями достичь, чем в sqlite это сделано.
Ни в каком другом open-source проекте такой помешанности на тестах не встречал. В sqlite кода тестов в 1000+ раз больше, чем собственно кода проекта, даже с учетом того, что многие тесты написаны на более высокоуровневом Tcl. Всем рекомендую почитать www.sqlite.org/testing.html — душераздирающее чтиво :)
Кстати, это же ipython? Тем через %timeit можно замеры делать — он и количество итераций сам выберет, и несколько раз бенчмарк прогонит, и сборщик мусора отключит, как-то так:
А по реализации — через RawQuerySet этот хак не получается сделать? Туда и query можно передать готовый (не raw_query), и params + логика по построению моделей более хитрая уже реализована — например, части ответа могут быть доступны как атрибуты модели, но не будут передаваться в конструктор (какое-нибудь вычисляемое в sql-запросе поле, например). Сам не пробовал, но код похоже выглядит.
2) Не очень приятная штука — в Group.objects.filter(user__id=12345).values('name') используется user__id, а в ParametrizedQuery — user_id. Было б удобно, если бы все было одинаково, или хотя бы было очевидно, как имена получать. Ведь если бы запрос был с user__username, нужно было бы писать не user_username, а просто username, так? Или еще что-то другое? Это все неочевидно довольно.
3) Пример из реального кода не понял — зачем там 12345. Ну и код с багами на потокобезопасность — у вас общий query на все потоки (т.к. он атрибут myview), execute меняет некоторые атрибуты query (self.places, например) — в момент вызова self.cursor.execute(self.sql,self.places) уже нельзя гарантировать, что в self.places были на основе **kw из этого потока построены.
Тут, мне кажется, 2 вещи: (а) .execute не должен менять состояние и (б) подготовленный запрос создать бы вне вьюхи (лучше всего — в models.py или managers.py; самое правильное — вообще в менеджере или в кастомном QuerySet для модели) — там же ничего зависящего от request нет, и несколько экземпляров не нужны, если execute состояние менять не будет.
+1 к этим проектам. Чего тут комментировать) В scikit-learn собрана куча современных алгоритмов, довольно неплохо оптимизированных, и люди все это на практике используют. В PyBrain — только небыстрые и не супер-актуальные нейронные сети + довольно корявые биндинги для SVM, которые, похоже, не очень-то и поддерживаются. Даже если количество коммитов сравнить — в PyBrain их за последний год штук 10 было, в scikit-learn это сотни (по десятку в день), очень активный и хороший проект. Pandas не пользовался, но все хвалят очень.
Внутри trie — тоже автомат, он тоже строится (при заполнении trie), другое дело что дополнительно не минимизируется. В итоге довольно похоже получается, если на конкретные действия смотреть, которые программы выполняют при поиске (взяли букву, перешли к следующей и т.д.) Плюс иногда trie еще в DAWG минимизируют, там еще более похоже выйдет.
Окончания с привязанными правилами в mystem, судя по бумаге, тоже хранятся, но не для всех слов («The boundary between stem and suffix is taken either from the input file if it is explicitly presented or computed automatically as the length of the common part of all word forms in the paradigm.») — информация о том, как бить слово на 2 части — это и есть аналог правил из aot (если я все правильно понял). Там, где размеченного вручную (лингвистически осмысленного) разбиения слов нет, работает автоматика.
По всей видимости, ручное указание разбиения необходимо, чтоб предсказание неизвестных слов работало лучше. Но это я, понятно, только гадать могу, т.к. mystem не делал и тонкостей не знаю.
И еще есть словари hunspell ( code.google.com/p/hunspell-ru/ ).
Еще пилю github.com/kmike/pymorphy2 потихоньку — там основа готова (подготовка словарей из OpenCorpora, разбор слов по словарю, предсказатель, работа с Cython-расширениями и без них — все со скоростью порядка 100тыс слов/сек и потреблением памяти порядка 15Мб) — нужно подописывать еще документацию, выложить скомпиленные словари и релиз сделать, но, мне кажется, в список тоже добавлять можно.
В 1.4, впрочем, заглушку добавят, наверное — да и ничто не мешает просить пользователей в settings руками настройку добавить так-то.
Тут пока нечего допиливать. Вот добавили новое правило, как проверить, лучше стало разбирать или хуже (precision, recall)? А никак сейчас. Что-то, возможно, лучше стало разбирать, а что-то хуже. Добавили «тью» для числительных, солист Muse стал числительным.
Допиливание в текущем виде не приближает к идеалу (и imho является напрасной тратой времени), т.к. критериев для добавления/изменения/удаления правил нет.
Чтоб были критерии какие-то, нужна какая-то оценка качества разбора. Код нужно поэтому писать для оценки качества разбора (анализатор написали уже), а на основе этих оценок уже выбирать правила (если уж собрались их вручную собирать).
Самое простое — это прогнать словарь русского языка через функцию и посмотреть количество правильных — неправильных — лишних вариантов разбора (вот и выяснится, кого там больше, числительных или существительных с тью, и какое правило правильней добавить будет).
… и мы опять пришли к словарю — не проще-продуктивнее ли тогда написать программу, которая сама правила подберет, чтоб оценка разбора была максимальной, вместо того, чтоб пробовать правила самим?
Но подход в статье и правда принципиально неправильный: выдумывать эти закономерности от балды — вместо того, чтобы выявить их из словаря + возможно, какой-то частотной статистики. Тут, в принципе, код анализатора даже имел бы право на жизнь, если б данные не от балды были, а какие-то осмысленные.
Со словарем этот же набор правил (окончание => часть речи) можно построить автоматически, более полно и правильно (что и делается в phpmorphy и большинстве других морф. анализаторов для русского языка). Благо словари для русского языка доступные и хорошие: см., например, opencorpora.org/dict.php.
Кроме того, раз уж есть словарь, то необязательно полагаться только на предсказатель — если слово есть в словаре, то можно и точный разбор вернуть (ну с учетом неустранимой на уровне отдельных слов неоднозначности разбора).
Кроме того, хранение всего в линейных массивах должно ускорять работу, т.к. данные префетчатся в кеш процессора (а хождение по указателям для современных процессоров — это кошмар, т.к, нужно брать данные из разных участков памяти и пре-заполнение кеша не работает). По скорости самым быстрым считается HAT-trie, в котором структура данных спроектирована именно исходя из интересов современных процессоров, чтоб данные в кеш процессора попадали (но там гибрид trie и хэш-таблицы получился, и из-за этого всякие trie-операци медленные и корявые).
* trec ( trec.nist.gov/data.html )
* собрание на amazon ( aws.amazon.com/datasets?_encoding=UTF8&jiveRedirect=1 )
* можно брать наборы url-ов c alexa.com
* archive.ics.uci.edu/ml/datasets.html
ну и т.д. ( см., например, www.quora.com/Data/Where-can-I-get-large-datasets-open-to-the-public )
В libdatrie достаточно большие накладные расходы на поддержку юникода: для каждого символа производится преобразование между «внешним» алфавитом и внутренним, и время поиска зависит линейно от количества интервалов во внешнем алфавите. Т.е. сравнение времени поиска не совсем 1 к 1 (вопрос о полезности этой фичи — отдельный).
К тому же в libdatrie каждому ключу сопоставляется целое число (это +4 байта к каждому ключу), а в вашей реализации нет, поэтому замеры памяти нечестные :)
Префиксные деревья, кстати, довольно плохо текстовую информацию все-таки сжимают. Самая эффективная схема хранения пока, насколько знаю, — это LOUDS-trie (в котором данные упаковываются с помощью разных битовых трюков). Есть MARISA-trie code.google.com/p/marisa-trie/, в котором строки хранятся в LOUDS-trie, а остатки не хранятся «как есть», а помещаются в LOUDS-trie следующего уровня (поэтому «рекурсивное trie») — на моих данных (3млн русских слов в utf8) marisa-trie тратит примерно в 10 раз меньше памяти, чем lidatrie. При этом каждому ключу в MARISA-trie тоже сопоставляется значение (4байтовое целое число), но это число не произвольное, а получается из ключа с использованием perfect hash-функции (которая вычисляет значение на основе положения ключа в дереве) — и поэтому эти значения памяти не требуют совсем.
Но MARISA-trie — это хак, причем я так и не понял, зачем он) Эта схема не поддерживает вставку новых значений и удаление существующих, а раз так, то MARISA-trie становится просто небыстрым не до конца минимизированным DAWG.
В DAWG текстовые данные занимают еще меньше места, т.к. строится минимальный автомат для данных строк. Те же 3 млн русских слов в utf8 в DAWG занимают меньше 3М с учетом значений (в 30+ раз меньше, чем в libdatrie) в реализации code.google.com/p/dawgdic/ — это DAWG, который основан на минимизации Double-Array Trie (той же структуры, что и в libdatrie).
Если интересно, еще обзор различных структур данных делал (применительно к питону, на английском, с уклоном в префиксные деревья): kmike.ru/python-data-structures/
Ни в каком другом open-source проекте такой помешанности на тестах не встречал. В sqlite кода тестов в 1000+ раз больше, чем собственно кода проекта, даже с учетом того, что многие тесты написаны на более высокоуровневом Tcl. Всем рекомендую почитать www.sqlite.org/testing.html — душераздирающее чтиво :)
%timeit list(u.groups.all())1) Вроде лучше было в бенчмарках использовать
.values_list('name', flat=True)вместо
[g['name'] for g in u.groups.values('name')].2) Не очень приятная штука — в Group.objects.filter(user__id=12345).values('name') используется user__id, а в ParametrizedQuery — user_id. Было б удобно, если бы все было одинаково, или хотя бы было очевидно, как имена получать. Ведь если бы запрос был с user__username, нужно было бы писать не user_username, а просто username, так? Или еще что-то другое? Это все неочевидно довольно.
3) Пример из реального кода не понял — зачем там 12345. Ну и код с багами на потокобезопасность — у вас общий query на все потоки (т.к. он атрибут myview), execute меняет некоторые атрибуты query (self.places, например) — в момент вызова
self.cursor.execute(self.sql,self.places)уже нельзя гарантировать, что в self.places были на основе **kw из этого потока построены.Тут, мне кажется, 2 вещи: (а) .execute не должен менять состояние и (б) подготовленный запрос создать бы вне вьюхи (лучше всего — в models.py или managers.py; самое правильное — вообще в менеджере или в кастомном QuerySet для модели) — там же ничего зависящего от request нет, и несколько экземпляров не нужны, если execute состояние менять не будет.
Окончания с привязанными правилами в mystem, судя по бумаге, тоже хранятся, но не для всех слов («The boundary between stem and suffix is taken either from the input file if it is explicitly presented or computed automatically as the length of the common part of all word forms in the paradigm.») — информация о том, как бить слово на 2 части — это и есть аналог правил из aot (если я все правильно понял). Там, где размеченного вручную (лингвистически осмысленного) разбиения слов нет, работает автоматика.
По всей видимости, ручное указание разбиения необходимо, чтоб предсказание неизвестных слов работало лучше. Но это я, понятно, только гадать могу, т.к. mystem не делал и тонкостей не знаю.