О сервисе WebGround

Ваша тема


Новости сайта

Литература

обложка книгиИнтернетика. Навигация в сложных сетях: модели и алгоритмы
Большакова Е.И., Клышинский Э.С., Ландэ Д.В., Носков А.А., Пескова О.В., Ягунова Е.В. Автоматическая обработка текстов на естественном языке и компьютерная лингвистикаАвтоматическая обработка текстов на естественном языке и компьютерная лингвистика (pdf)
Ягунова Е.В., Макарова О.Е., Антонова А.Ю., Соловьев А.Н. Разные методы компрессии в исследовании понимания новостного текстаРазные методы компрессии в исследовании понимания новостного текста (pdf)
Крылова И.В, Пивоварова Л.М., Савина А.В., Ягунова Е.В. Исследование новостных сегментов российской «снежной революции»: вычислительный эксперимент и интуиция лингвистовИсследование новостных сегментов российской «снежной революции»: вычислительный эксперимент и интуиция лингвистов (pdf)
Ягунова Е.В. Исследование перцептивной устойчивости фонем как элементов речевой цепиИсследование перцептивной устойчивости фонем как элементов речевой цепи (pdf)
Ягунова Е.В. Вариативность структуры нарратива и разнообразие стратегий пониманияВариативность структуры нарратива и разнообразие стратегий понимания (pdf)
Ягунова Е.В., Пивоварова Л.М. Экспериментально-вычислительные исследования художественной прозы Н.В. ГоголяЭкспериментально-вычислительные исследования художественной прозы Н.В. Гоголя (pdf)
Ягунова Е.В. Вариативность стратегий восприятия звучащего текстаВариативность стратегий восприятия звучащего текста (pdf)
Ягунова Е.В. Спонтанный нарратив у детей и у взрослыхСпонтанный нарратив у детей и у взрослых (pdf)
Ягунова Е.В. Исследование избыточности русского звучащего текстаИсследование избыточности русского звучащего текста (pdf)
Ягунова Е.В. Фонетические признаки опорных сегментов и восприятие русского текстаФонетические признаки опорных сегментов и восприятие русского текста (pdf)
Ягунова Е.В. Коммуникативная и смысловая структура текста и его восприятиеКоммуникативная и смысловая структура текста и его восприятие (pdf)
Ягунова Е.В. Где скрывается смысл бессмысленного текста?Где скрывается смысл бессмысленного текста? (pdf)
Ягунова Е.В. Эксперимент в психолингвистике: Конспекты лекций и методические рекомендацииЭксперимент в психолингвистике: Конспекты лекций и методические рекомендации (pdf)
Ягунова Е.В. Теория речевой коммуникацииТеория речевой коммуникации (pdf)
Антонова А.Ю., Клышинский Э.С., Ягунова Е.В. Определение стилевых и жанровых характеристик коллекций текстов на основе частеречной сочетаемостиОпределение стилевых и жанровых характеристик коллекций текстов на основе частеречной сочетаемости (pdf)
Ягунова Е.В. Эксперимент и вычисления в анализе ключевых слов художественного текстаЭксперимент и вычисления в анализе ключевых слов художественного текста (pdf)
Ягунова Е.В. Ключевые слова в исследовании текстов Н.В. ГоголяКлючевые слова в исследовании текстов Н.В. Гоголя (pdf)
Пивоварова Л.М., Ягунова Е.В. Информационная структура научного текста. Текст в контексте коллекцииИнформационная структура научного текста. Текст в контексте коллекции (pdf)
Савина А.Н., Ягунова Е.В. Исследование коллокаций с помощью экспериментов с информантамиИсследование коллокаций с помощью экспериментов с информантами (pdf)
Ягунова Е.В., Пивоварова Л.М. От коллокаций к конструкциямОт коллокаций к конструкциям (pdf)
Пивоварова Л.М., Ягунова Е.В. Извлечение и классификация терминологических коллокаций на материале лингвистических научных текстовИзвлечение и классификация терминологических коллокаций на материале лингвистических научных текстов (pdf)
Julia Kiseleva. Grouping Web Users based on Query LogGrouping Web Users based on Query Log (pdf)
Julia_Kiseleva_Unsupervised_Query_Segmentation_Using_Click_Data_and_Dictionaries_Information.pdfUnsupervised Query Segmentation Using Click Data and Dictionaries Information (pdf)
Четыре лекции о методе
Начала предметного анализа методов (на примере метода Ф.Бэкона)
Вариативность стратегий восприятия звучащего текста
Извлечение и классификация коллокаций на материале научных текстов. Предварительные наблюдения
Природа коллокаций в русском языке. Опыт автоматического извлечения и классификации на материале новостных текстов
Войтишек А. Повторы. Лирические рефреныПовторы. Лирические рефрены (pdf)
Войтишек А. Новое. Лирические рефреныНовое. Лирические рефрены (pdf)
Войтишек А. Всё об одном и том жеВсё об одном и том же. 500 лирических рефренов к 50-летию (pdf)
Войтишек А. Тысяча-часть-1Тысяча-часть-1 (pdf)
Войтишек А. Тысяча-часть-2Тысяча-часть-2 (pdf)
Войтишек А. АлфавитАлфавит (pdf)

5.4. Метод суффиксных деревьев

 

Изначально метод суффиксных деревьев (Suffix Tree Clustering) был разработан для быстрого поиска подстрок в строках.

Суффикс  строки  - это такая строка, в которой конкатенация  (сцепление строк) совпадает с  для некоторой (возможно, пустой) строки . Суффикс называется собственным, если  Например, для строки «substring» подстрока «sub» является собственным префиксом, «ring» — собственным суффиксом. Срока  называется при этом префиксом.

Суффиксное дерево – это дерево, содержащее все суффиксы строки. Оно состоит из вершин, ветвей и суффиксных указателей (меток). Метка узла в дереве определяется как конкатенация подстрок, маркирующих ребра пути от корня дерева до этого узла.

 Существуют алгоритмы (например, алгоритм Укконена (E. Ukkonen) [143]), реализующие построение суффиксных деревьев за  шагов, где  - длина строки. Ветви дерева обозначаются отдельными буквами или частями суффиксов строки. Суффикс, соответствующий определенной вершине, можно получить путем объединения букв, которые находятся на ветвях, начиная от корневой вершины и заканчивая данной.

Рассмотрим простейший вариант построения суффиксного дерева, формируемого «налету», по мере поступления новых символов в «хвост» строки. Пусть  строка  в окончательном виде состоит из последовательности символов  Вводится понятие префикса, т.е. последовательности символов  начало строки . Суффиксное дерево строится не только для всей строки, но и для всех ее префиксов. Рассмотрим алгоритм детальнее по шагам:

0. Строится суффиксное дерево для .

1. Суффиксное дерево расширяется путем добавления ветвей .

. . .

n - 1. Суффиксное дерево для  расширяется до дерева для .

n. Суффиксное дерево для  расширяется до дерева для  ($ - конец текста).

Последовательность шагов приведенного алгоритма для строки abca$ приведена на рис. 20.

В настоящее время идеология суффиксных деревьев применяется для кластеризации результатов работы информационно-поисковых систем в интерактивном режиме. Именно такой подход используется, например, на поисковых серверах Clusty (http://www.clusty.com) или Nigma (http://www.nigma.ru). Остановимся подробнее на принципах построения и применения суффиксных деревьев в случае, когда в качестве текстовой строки используется весь текст документа, а в качестве символов – слова.

 

Рис. 20. Процесс построения суффиксного дерева

 

Вначале при построении дерева документы, получаемые от поисковой системы, подвергаются отчистке от пунктуации, слова из документов приводятся в канонические формы (лемматизация) и т.д. После этого для найденных документов строится суффиксное дерево, но в этом случае ветвям приписываются термы (слова или словосочетания), а не буквы как при традиционном подходе. В результате вершинам дерева соответствуют фразы, которые можно получить, объединив все термы, находящиеся на ветвях, ведущих от корня к данной вершине дерева. В вершинах дерева, имеющих потомков, расположены ссылки на документы, в которых встречается фраза, соответствующая вершине.  Ее можно получить, объединив все слова, находящиеся на ребрах на пути от корня дерева к данной вершине.  Множества документов, на которые указывают эти ссылки, образуют базовые кластеры. Затем происходит укрупнение базовых кластеров и получение окончательного набора кластеров. На рис. 21 приведено суффиксное дерево для предложения «I know you know I know». 6 узлов в этом примере маркированы как прямоугольники с цифрами от 1 до 6.

Рис. 21 . Пример суффиксного дерева для одного предложения

 

Суффиксное дерево можно генерировать также из нескольких предложений. На рис. 22 приведен пример общего суффиксного дерева для трех предложений «cat ate cheese», «mouse ate cheese too» и «cat ate mouse too».  Внутренние узлы на данном графе представлены как кружки, которые отмечены буквами от a до f. Одиннадцать листьев в этом примере маркированы прямоугольниками, первая цифра в которых – номер предложения, из которого взят суффикс, а вторая цифра – позиция в предложении.

Кластеры определяются на основе близости между множествами документов, соответствующих узлам суффиксного дерева, следующим образом. Пусть   и  – базовые кластеры,  - их размеры. количество общих документов для этих кластеров. Близость  между  и  задается условием:

где  некоторый порог, принимающий значение от 0 до 1, например 0,6.

ris22-02

Рис. 22. Пример общего суффиксного дерева для нескольких предложений

 

На рис. 23. показаны результаты формирования кластеров для случая, приведенного на рис. 22 с 6-ю узлами (от a до f). В случае а порог  в случае b в случае c порог также равен 0.6, однако слово ate исключено с помощью «стоп-словаря».

В отличие от большинства моделей кластеризации, рассматривающих текст как “Bag of Words”, в методе суффиксных деревьев учитывается порядок слов, что существенно влияет на учет лингвистических особенностей группируемых текстов. В отличие от многих других методов, кластеры, сформированные с помощью метода суффиксных деревьев могут пересекаться, что вполне соответствует реальности.  К достоинствам этого метода можно отнести также его наглядность представления результатов и высокую скорость работы.