Зависимость роста количества триграмм от размера словаря.

Произвёл более детальный анализ количества слов и триграмм.
Общее число слов в выбранных книгах: 554928 слов.
Число уникальных слов в книгах: 57703 слова.
Число триграмм: 8340.

Зависимость количества триграмм от количества слов.
Красным цветом на графике отображено масштабированное значение производной. Синим цветом - количество триграмм.


Частотность встречаемости триграмм

Представлена гистограмма распределения "популярности" триграмм. Полезных данных на этой гистограмме разглядеть не удаётся, потому вот некоторые её характеристики:
Триграмма встречается от 1 до 10 раз - 2622 штук
Триграмма встречается от 1 до 100 раз - 5298 штук.
Наиболее популярные триграммы имеют частоты: 25736, 23366, 22604, 19849, 18060, 16947, 16267 и 16259.
Приведу пример триграмм встречающихся 1 раз.
[хуя] => [хуянь]
[уян] => [хуянь]
[чжо] => [чжо]
[чжэ] => [чжэня]
[жэн] => [чжэня]
[эня] => [чжэня]
[бао] => [бао]
[усю] => [дусю]
[биа] => [лабиальности]
[фюз] => [фюзеляжа]
[юзе] => [фюзеляжа]
[ияд] => [внутриядерную]
[ыяв] => [выявивших]
[уиц] => [интуиция]
[зущ] => [ползущим]
[ехз] => [четырехзначную]
[хзн] => [четырехзначную]
[фмо] => [логарифмов]
[нкм] => [инкм]
[адг] => [адгезивы]
[дге] => [адгезивы]
[гез] => [адгезивы]
[кюв] => [кюветах]
[ымр] => [вымрут]
[мтя] => [ломтя]
[брь] => [сентябрьская]
[рхм] => [сверхмощной]
[йга] => [тайга]
[ухк] => [двухкилометровое]
[йсм] => [сейсмостанции]
[нза] => [вонзаются]
[оео] => [своеобразная]
[улл] => [буллиальд]

Видно, что редкие триграммы можно разбить на несколько категорий:
- редкие слова,
- слова не специфичные для взятых текстов,
- иностранные слова, записанные русскими буквами (здесь же и иностранные имена).
- слова с ошибками.

Выводы
Каждое слово в тексте повторяется в среднем 10 раз. Судя по скорости прибывания триграмм, можно уверенно сделать вывод, что либо количество триграмм в русском языке не ограниченно небольшим числом, либо текущая выборка слов недостаточна для работы с русским текстом и следует расширить выборку текстов. Так как по первому пути (отказаться от триграмм) всегда можно пойти, сейчас следует пойти по второму пути и увеличить объём анализируемых текстов. В будущем стоит расширить исходный текстовый материал специфическими статьями и научными работами. Стоит добавить в анализируемые тексты перечни числительных и имён. При разработке, вероятно, можно будет добавить в качестве параметра возможность управления весом характеристик. Вероятно, что при достаточно большой выборке текстов, можно будет из списка найденных триграмм исключить редкие триграммы.

[Для себя. Следующий шаг работы - расширить библиотеку текстов, автоматизировать текущий анализ и добавить возможность кеширования результатов, ибо текущая скорость анализа (около 2 минут) не устраивает.]

Триграммы русского языка

Что такое триграмма?
Триграммой я называю любую комбинацию из трёх букв или пробела. Идею триграмм я почерпнул у Джо Армстронга (книга Programming Erlang).

В чём состоит идея?
Задача: предсказать может ли произвольная комбинация букв являться английским словом. Для решения Джо предлагает взять полный список английских слов. Добавить в начало и в конец каждого слова символ пробела и собрать все реально существующие триграммы. Например, для слова love будут следующие триграммы " lo", "lov", "ove" и "ve ". В принципе, идея довольно очевидна, триграмма qqq не может существовать ни в одном английском слове. Для русского языка можно аналогично сказать, что триграмма ттт не может встретиться ни в одном русском слове.

Исходный материал
Для исследования выбраны тексты из электронной библиотеки Мошкова.
Л.Н.Толстой Анна Каренина
А. и Б. Стругацкие Страна багровых туч
А. и Б. Стругацкие Страна багровых туч (другая редакция)
А. и Б. Стругацкие Путь на Амальтею
А. и Б. Стругацкие Стажеры
А. и Б. Стругацкие Хищные вещи века
А. и Б. Стругацкие Шесть спичек
А. и Б. Стругацкие Забытый эксперимент

Толстой выбран из-за обилия материала, а также из-за наличия в тексте некоторого числа устаревших слов. Стругацкие же были выбраны как авторы писавшие на относительно современном русском языке, а также из-за моего пристрастия к фантастике.

Стоит также отметить особенность электронных текстов. В них огромное количество ошибок. Большая часть этих ошибок - ошибки распознавания текста. В некоторых случаях на эти ошибки можно не обращать внимания. Однако стоит иметь их в виду.

Статистические данные по текстам
Зависимость количества триграмм от числа слов

книга	всего слов	уникальных слов	количество триграмм
books/0	270110	32830	6835
books/1	77341	18960	6452
books/2	70566	18045	6378
books/3	19337	5852	4752
books/4	58204	13325	6052
books/5	48237	12758	5969
books/6	5180	2329	3286
books/7	5967	2512	3478

Выводы
Хоть и не очень убедительно, но видна зависимость числа триграмм от общего числа уникальных слов. Кроме того, видно, что число триграмм, если и не стремится к конкретному числу, то по крайней мере сильно замедляет свой рост с ростом общего количества слов. Потому, следует провести более точное построение кривой. Вероятно, будет также интересна гистограмма "популярности" триграмм в словах.

Програмный анализ русского текста

Решил реализовать давно вертевшуюся в голове идею программного анализа русскоязычного текста. В анализ входит разбор слов по частям речи и определение словоформ, а также анализ предложений на их части. В результате должна получиться "идеальная" система для проверки орфографии и пунктуации.

Исследование разбивается на несколько этапов.
1) Анализ текста в целом.
2) Анализ отдельных слов.
3) Анализ словосочетаний.
4) Анализ предложений.

Посты постараюсь организовать небольшими и исключительно с результатами исследований.

Сравнение MySQL и PostgreSQL с точки зрения разработчика

Аннотация

В статье представлен сравнительный анализ двух бесплатных свободных систем управления базами данных (СУБД): MySQL и PostgreSQL. Анализ ведётся с точки зрения использования этих СУБД в мало- и средненагруженных приложениях. Не рассматриваются вопросы масштабирования и оптимизации под проекты с многомиллионными аудиториями. Не приводятся данные сравнения производительности. Рассматриваются MySQL 5.1 и PostgreSQL 8.3.

Типы данных

Первое с чем приходится сталкиваться разработчику - это доступные типы данных. Проведём сравнение доступных типов данных.

Целые числа и числа с плавающей точкой

Я не буду указывать диапазоны возможных значений, однако укажу информационную ёмкость в байтах.

.                       |MySQL                | PostgreSQL        
TINYINT                 |1 байт               |                   
SMALLINT                |2 байта              | 2 байта           
MEDIUMINT               |3 байта              |                   
INTEGER, INT            |4 байта              | 4 байта           
BIGINT                  |8 байт               | 8 байт            
FLOAT, DOUBLE, REAL     |4 или 8 байт         | 4 или 8 байт      
DECIMAL, NUMERIC        |65 десятичных знаков | без ограничений   
SERIAL, BIGSERIAL       |8 байт               | 4 или 8 байт
BIT                     |он есть              | он есть

Примечание:
1) В MySQL есть поддержка UNSIGNED типов, однако это не входит в стандарт SQL.
2) Для типов с плавающей точкой PostgreSQL использует формат стандарта IEEE 754, поэтому можно хранить значения +Inf, -Inf и NaN, однако использовать эти значения в математических операциях не выйдет.


Как видно из таблицы, типы данных практически идентичны для двух СУБД. Различия состоят в том, что MySQL позволяет более детально использовать доступную память, но при этом работа с числами в символьном представлении ограничена 65 цифрами. Я не вижу ни одного практического применения числам с таким количеством знаков, потому можно считать что возможности MySQL и PostgreSQL в данном разделе идентичны.

Строки и данные

Размеры указываются в байтах. Не забывайте, что для одного символа UTF-8 может использоваться от 1 до 4 байт.

.                       | MySQL           | PostgreSQL
BINARY, CHAR            | 255             | 10485760
VARCHAR, VARBINARY      | 65535*          | 10485760
TINYBLOB,TINYTEXT       | 2^8             | 
BLOB, TEXT, bytea       | 2^16            | не ограничен
MEDIUMBLOB              | 2^24            | 
LONGBLOB                | 2^32            |

* ограничение вызвано максимальной длиной строки, равной 65535 байтам, но в реальности максимальная длинна гораздо меньше.


Из таблицы видно, что по ёмкости строковые типы данных в двух СУБД практически не различаются, и снова MySQL позволяет более детально контролировать формат хранения данных на жёстком диске. Однако эта гибкость MySQL вводит две небольшие проблемы на этапе проектирования: сумятицу в типах и размерах данных.

Чтобы не быть голословным приведу пример — хранение данных пользователя. Предположим, что нам потребовалось хранить о пользователе не только его имя, фамилию и отчество, но адрес и телефоны, да мало ли что мы можем предложить хранить пользователю в своём профиле. С точки зрения SQL для этого должны использоваться типы CHAR и VARCHAR. И вот тут в MySQL приходится решать какая максимальная длинна у фамилии, какая максимальная длинна у имени, какая максимальная длинна у адреса, ибо на всё про всё дано 65535 байт. В то же время в PostgreSQL мы просто указываем в качестве типа для всех столбцов таблицы VARCHAR, куда мы в случае необходимости можем уложить гораздо больше данных, чем нам позволяет MySQL. (Попрошу не предлагать использовать TEXT в MySQL для этих целей.)

Дата и время

Типы даты и времени для двух баз практически идентичны и проблем как правило не вызывают.

Нестандартные типы

Для желающих PostgreSQL предлагает целую группу типов данных для работы, которые напрочь отстутствуют в MySQL: массивы, структуры, типы для хранения IP и MAC адресов, и даже типы для хранения параметров геометрических фигур. Желающие могут самостоятельно ознакомиться с типами данных PostgreSQL.

Выводы по типам данных

1) Типы данных, предлагаемые двумя СУБД, с функциональной точки зрения идентичны.
2) При помощи этих типов можно хранить данные в любой из СУБД, однако в MySQL разработчик вынужден на самом начальном этапе проектирования искуственно ограничивать длинну строковых данных, что не сказывается положительно на удобстве пользования системой.
3) Использование нестандартных типов в PostgreSQL позволяет довольно сильно упростить разработку, однако усложнит переход на другую СУБД.
4) MySQL позволяет точно контролировать структуру хранимых данных, однако при этом жертвуется удобством разработчика.

Возможности управления данными

Здесь я хочу сравнить две СУБД с точки зрения дополнительного функционала предлагаемого разработчику. Часть этого функционала включена в стандарт SQL.

Хранимые процедуры

Начнём с простейшего — хранимые процедуры. Грубо говоря, в MySQL вообще нет функционала хранимых процедур. Если выражаться более точно, то вообще они есть, но довольно условны. Так, например, при включённой репликации хранимые процедуры могут быть только readonly. Так что довольно популярная схема ограничения прав пользователя через хранимые процедуры вовсе не реализуема на MySQL.

Индексы и ключи

На этом фронте MySQL тоже не блещет своими возможностями. Ограничение в 1000 байт на размер ключа — куда это годится? Допустим, я разрешаю своим пользователям создавать учётные записи на любом языке (UTF-8). В качестве максимальной длинны логина я выбираю 512 символов. Так как логины должны быть уникальными, прихожу к выводу, что нужно наложить уникальный ключ на столбец, и, как выясняется, не могу, ибо ключ не вписывается в 1000 байт. Приходится идти на уступки и делать уникальность только по первым 333 символам. Кто не верит, может самостоятельно посмотреть на результат create table t( t varchar(512), key(t)) character set = utf8.
PostgreSQL такими комплексами не страдает, а просто делает уникальный ключ необходимого размера.

Проверка данных на этапе добавления

В стандарте SQL была предусмотрена инструкция CHECK, которая задаёт выражение, которому должны удовлетворять данные добавляемые в таблицу. В руководстве MySQL об этой инструкции сказано предельно просто «The CHECK clause is parsed but ignored by all storage engines.» Больше добавить мне к этому нечего, в постгре, как и ожидалось, всё в порядке.

Транзакции и внешние ключи

По умолчанию в MySQL для таблиц используется движок MyISAM, который не поддерживает ни транзакций ни внешних ключей. Это сложилось исторически и у такого подхода есть оправдание, если рассматривать работу с БД с точки производительности. Можно просто заметить, что, если вам нужны транзакции и внешние ключи, то использование storage engine InnoDB обязательно. Естественно в PostgreSQL транзакции и вешние ключи полностью функциональны.

Выводы

MySQL и PostgreSQL — это системы управления базами данных, перед которыми стоят разные задачи и стоит чётко понимать, в чём их разница. В качестве практических рекомендаций могу сказать, что MySQL показывает своё преимущество в области HighLoad, однако требует более внимательного подхода со стороны разработчика, а также накладывает довольно серьёзные ограничения на хранимые данные и на функциолнал СУБД.

Вобщем, для проектов не ориентированных на многомиллионную посещаемость, а также в академических целях я рекомендую использовать PostgreSQL. Это позволит сильно упростить разработку и отладку приложений. MySQL показывает своё преимущество исключительно на базах данных с большим количеством простых однотабличных запросов и требует к себе пристального внимания со стороны разработчкиа.


_________
Текст подготовлен в ХабраРедакторе

Не используйте MyISAM (MyISAM vs InnoDB)

Прочитав большое количество отзывов и рекомендаций про работу InnoDB и MyISAM, я обнаружил пример, который меня убедил, что MyISAM следует использовать предварительно подумав 10 раз. А для повседневной разработки стоит использовать только InnoDB.

Краткое сравнение:

• InnoDB поддерживает внешние ключи и транзакции и потому поддерживает целостность данных. MyISAM не делает ничего из перечисленного.
• InnoDB устойчив к отключению питания. MyISAM может потерять данные при отключении питания.
• InnoDB требует для хранения информации больше дискового пространства чем MyISAM.
• Производительность InnoDB практически не уступает MyISAM (бенчмарки). Стоит также учесть, что при соотношении запросов 10 выборок на одну запись MyISAM может выигрывать в производительности (рассмотрение этого вопроса выходит за рамки данной заметки, материал легко найти в интернете)
  
• InnoDB несколько хуже масштабируется (для подавляющего большинства проектов это не требуется).
• У InnoDB есть несколько серьёзных и в то же время забавных ограничений (ограничения).
  

А теперь позвольте привести пример, который повёрг меня в сильный ступор.

Пример:

mysql> CREATE TABLE t (a INT NOT NULL, UNIQUE(a) ) ENGINE=MyISAM;
Query OK, 0 rows affected (0.01 sec)

mysql> INSERT INTO t values (5), (6);
Query OK, 2 rows affected (0.00 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> select * from t;
+---+
| a |
+---+
| 5 |
| 6 |
+---+
2 rows in set (0.00 sec)

mysql> update t set a = 1;
ERROR 1062 (23000): Duplicate entry '1' for key 1
mysql> select * from t;
+---+
| a |
+---+
| 1 |
| 6 |
+---+
2 rows in set (0.00 sec)

Как видно, что при использовании MyISAM малейшая ошибка может вызвать полную потерю информации. Можно даже с уверенностью утверждать, что целостность данных будет нарушена. С InnoDB такого бы не произошло. Для себя я сделал вывод, что при разработке следует использовать InnoDB, но не злоупотреблять её преимуществами, ибо всегда есть вероятность того, что придётся переходить на MyISAM в целях оптимизации.

P.S. А вообще, не стоит использовать MySQL, лучше использовать PostgreSQL, но эту тему я раскрою несколько позже.

Кодировки и MySQL

Проблема кодировок, пожалуй, первая проблема с которой сталкиваются пользователи MySQL начиная с 5 версии. "Вместо строки знаки вопроса", "Неправильная сортировка" таковы темы бесчисленных топиков создаваемых в интернете.
При работе с базой MySQL 5.x следует запомнить, что есть 2 основных кодировки - кодировка в которой хранятся данные и кодировка в которой передаются данные. Первая указывается при создании таблиц в базе, а вторая указывается непосредственно при соединении.
Предположим, я хочу хранить данные в UTF-8, добавлять в cp866, а получать их в cp1251. Работа будет проводиться в коммандной строке windows.

Пример:

C:\Server\mysql\bin>chcp 866
Текущая кодовая страница: 866

C:\Server\mysql\bin>mysql -uexample -pexample example
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 3 to server version: 5.0.18-nt

Type 'help;' or '\h' for help. Type '\c' to clear the buffer.

mysql> drop table strings;
Query OK, 0 rows affected (0.03 sec)

mysql> CREATE TABLE `strings` (string text) DEFAULT CHARACTER SET UTF8;
Query OK, 0 rows affected (0.14 sec)

mysql> set names cp866;
Query OK, 0 rows affected (0.00 sec)

mysql> INSERT INTO `strings` VALUES ('Строка'), ('Вопрос');
Query OK, 2 rows affected (0.01 sec)
Records: 2  Duplicates: 0  Warnings: 0

mysql> select * from `strings`;
+--------+
| string |
+--------+
| Строка |
| Вопрос |
+--------+
2 rows in set (0.00 sec)

mysql> \q
Bye

C:\Server\mysql\bin>chcp 1251
Текущая кодовая страница: 1251

C:\Server\mysql\bin>mysql -uexample -pexample example
Welcome to the MySQL monitor.  Commands end with ; or \g.
Your MySQL connection id is 4 to server version: 5.0.18-nt

Type 'help;' or '\h' for help. Type '\c' to clear the buffer.

mysql> select * from `strings`;
+--------------+
| string       |
+--------------+
| Строка |
| Р’РѕРїСЂРѕСЃ |
+--------------+
2 rows in set (0.00 sec)

mysql> set names cp1251;
Query OK, 0 rows affected (0.00 sec)

mysql> select * from `strings`;
+--------+
| string |
+--------+
| Строка |
| Вопрос |
+--------+
2 rows in set (0.00 sec)

mysql>

А теперь на словах. Я установил кодировку cp866, подключился к MySQL и создал таблицу, строки которой будут храниться в UTF-8. Затем, указал базе даннных, что сейчас данные будут в cp866 и добавил 2 записи в таблицу. Закрыл соединение с базой данных и изменил текущую кодовую страницу на cp1251. Снова соединился с базой данных и попробовал получить данные из таблицы. Мне пришла белиберда, так как база данных решила, что мне нужны данные в UTF-8. После того как я указал, что мне нужны данные в cp1251, база отдала мне их в нужной кодировке.

Таким образом, можно сделать вывод, что в MySQL можно хранить данные в UTF-8 вне зависимости от того в какой кодировке вы будете передавать и получать данные.

Заметки:

• После соединеня с MySQL необходимо отправлять команду SET NAMES <кодировка>, до отправки или получения данных.
• Кодировка в которой хранятся данные определяется при создании таблицы.

Чувствительность к регистру в MySQL

По умолчанию в MySQL строки (char, varchar, text) регистронезависимы. Таким образом строки "Пример" и "примеР" идентичны. Самым популярным решением сделать строки регистрозависимыми является использование типа blob. Однако это не правильно.

Во-первых, с BLOB не будут правильно работать строковые функции. Во-вторых перестанет работать механизм смены кодировки (подробнее об этом механизме я напишу позже).

Правильным же решением этой задачи является использование COLLATION. Слово COLLATION переводится как сличение, то есть задаёт правила сравнивания строк.

Пример:

CREATE TABLE `users` (
  `username` text NOT NULL,
  `host`   text NOT NULL,
  `password` text NOT NULL,
  `email`  text ,
  `uniqueid` text ,
  `datereg` TIMESTAMP NOT NULL DEFAULT CURRENT_TIMESTAMP
) ENGINE = MyISAM
DEFAULT CHARACTER SET UTF8 COLLATE UTF8_BIN;

* This source code was highlighted with Source Code Highlighter.

В данном примере для всех строк в таблице задаётся кодировка UTF-8 и задаётся правило регистрозависимого сравнения.

Заметки:

• Команда show collation; выводит список всех поддерживаемых сличений и их параметры.
• Наличие у сличения окончания _ci (например, utf8_general_ci) указывает, что оно регистронезависимо (case insensitive). Окончание _bin указывает, что сличение регистрозависимо (сравнивается в двоичном формате).
• Подробнее можно почитать тут: link


• Примеры использования:
  • для базы link
  • для таблицы link
  • для столбца link
  • даже при выборке или вставке link