Слова

В тексте непрерывные последовательности знаков (символьные цепочки) будем называть словами.

Определения.

• Частота - это количество вхождений слова в текст. Для данного экземпляра слова все его реплики в тексте будем называть клонами. Частота может быть равна единице.
• Длина слова - это количество знаков в нем.
• Адрес - смещение экземпляра слова от начала текста. Первое слово в тексте имеет нулевой адрес.
• Расширяемость. Экземпляр слова является расширяемым влево или вправо, если при присоединении к нему символа слева или справа частота слова не уменьшается. Нетрудно видеть, что если экземпляр слова имеет какую-то расширяемость, то такую же расширяемость имеют и все его клоны.
• Сжимаемость. Экземпляр слова является сжимаемым слева или справа, если при удалении символа слева или справа частота слова не увеличивается. Так же, как и в случае расширяемости, если экземпляр слова имеет какую-то сжимаемость, то такую же сжимаемость имеют и все его клоны.
• Мягкий критерий расширяемости или сжимаемости состоит в требовании, чтобы частота при манипуляциях с крайними символами слова изменялась не более, чем на заданную относительную величину.
• Слово называется правопредельным, если оно нерасширяемо вправо, но при этом сжимаемо справа. Аналогично определяется левопредельное слово. Слово, для которого выполняются оба критерия предельности называется предельным.

Ступеньки расширяемости.

В каждой точке текста начинается несколько слов. Если, начиная с одиночного символа, последовательно удлинять слова путем добавления символов справа, то могут появиться один или несколько интервалов длин, в которых слова являются расширяемыми вправо. На Рис. 1 показан пример зависимости частоты слов, начинающихся в одной точке, от их длины. По оси ординат откладывается десятичный логарифм частоты, графики получены на текстах длиной 150, 300 и 600 Мб, участок обработанного текста имеет вид: "_Однажды,_во_время_" (пробел здесь обозначен символом "_").

Видны три ступеньки в интервалах 6-8, 9-10 и 15-19, на которых частота не меняется, а слова являются расширяемыми вправо (кроме слов на концах ступенек).

Появление ступенек на графике зависимости частоты слов при последовательном удлинении связано со структурой языка. На Рис. 1 видно, что, при достижении цепочки " Однаж" продолжение становится однозначным (буквы д, ы). Поэтому присоединение этих букв не изменяет частоту слов (появляется ступенька). Аналогично, присоединение пробела после запятой в позициях 9, 10 также не меняет частоту. Слово "_Однажды,_во_в" содержит указание на время и во всех трех текстах во всех вхождениях получило одинаковое продолжение "ремя_", продемонстрировав расширяемость. Если бы в тексте существовала фраза " Однажды, во вторник", то это привело бы к сокращению области расширяемости (ширины ступеньки) до позиций 16-19.

Таким образом, на графике Рис. 1 можно выделить три правопредельных слова - структурные элементы языка: "_Однажды", "_Однажды,_" и "_Однажды,_во_время_".

Словари.

Термин "словарь" будем понимать в обычном смысле как упорядоченный перечень слов. Виды словарей:

• Полный словарь - содержит все слова;
• Частотно ограниченный словарь с параметром s - словарь, содержащий слова с частотой равной или превышающей s;
• Парциальный словарь содержит только слова с заданной частотой;
• Словари расширяемых, сжимаемых и предельных слов;

Продуктивное дерево

Продуктивное дерево отражает образование слов в процессе добавления символов справа. Узлам в продуктивном дереве соответствуют слова, а параметрами узлов являются длина и частота соответствующих слов. Будем рассматривать только слова с частотой больше 1. Связи в дереве ориентированны. Связь существует и направлена из узла 1 в узел 2, если слово 2 получается из слова 1 прибавлением одного знака в конце. Сумма частот дочерних узлов равна частоте родительского узла. Каждый узел имеет одну входящую связь и несколько выходящих. Исключениями являются узлы, состоящие из одного знака (вершины деревьев), у которых нет входящих связей, а также узлы-листья, у которых нет выходящих связей. Будем называть частотой связи частоту принимающего узла. Пути проходящие по связям с максимальной частотой будем называть траверсами. Траверсы могут разветвляться на узлах, имеющих несколько выходящих связей с одинаковой максимальной частотой. Траверса, выходящая из вершины дерева, ведет к конечному слову-листу, являющемуся уникальным для данной начальной буквы (и - для данного языка). Например, слово-фраза в конце траверсы, выходящей из начальной буквы "з", имеет вид "за столом сидели два".

Контрпродуктивное дерево строится аналогично продуктивному. Узлы верхнего уровня представляют собой отдельные символы. На втором уровне располагаются двухбуквенные слова, получаемые из символов верхнего уровня присоединением символов слева. Слова третьего уровня получаются из слов второго дальнейшем добавлением символов слева. Совокупности слов на уровнях у продуктивного и контрпродуктивного деревьев совпадают. Это дает возможность объединения деревьев в граф продуктивности. Траверсы в графе продуктивности строятся по совокупности связей с максимальной частотой. На траверсе начальный символ наращивается присоединением знаков как справа, так и слева. Та же буква "з" в конце траверсы на графе продуктивности превращается в фразу ". Он сидел за столом и писал".