Как машина "понимает" смысл текста...
Не все знают, что сочиненные людьми тексты имеют одинаковую структуру. Закономерность впервые обнаружил и сформулировал Джорж Зипф. Благодаря ему компьютеры научились "понимать" смысл текста и самостоятельно выделять ключевые слова.
Возьмем в качестве примера следующий фрагмент текста: "Не пейте водку из одноразовых стаканчиков. В пластик, из которого изготавливают одноразовую посуду, для прочности добавляют стабилизаторы - полистирол и полипропилен. Поэтому ее многократное использование чревато серьезными последствиями для вашего здоровья. При взаимодействии, например, с алкоголем стаканчики из этих материалов начинают выделять отравляющие вещества, которые постепенно накапливаются в организме. Так что водку из одноразовых стаканчиков лучше не пить" (фрагмент текста взят со страницы http://vodka.agava.ru).
Теперь посчитаем количество вхождений каждого слова в данный фрагмент текста. Эта величина называется частотой вхождения слова. Процесс подсчета довольно трудоемок и скучен, поэтому рекомендую использовать специальный апплет (www.shipbottle.ru/ir), реализующий этот метод. Получился следующий результат (приведена статистика для слов с частотой больше 1):
4 - из
2 - стаканчиков
2 - одноразовых
2 - не
2 - для
2 - водку
2 - в
Данный апплет имеет существенный недостаток: частота каждого термина вычисляется без учета морфологии. Данную проблему легче всего решить, используя "Грамматический словарь русского языка", составленный Зализняком. Этот словарь очень хорошо отражает современное словоизменение, то есть для каждого входящего в словарь слова даны сведения о том, изменяемо ли оно, и если да, то как именно оно склоняется и спрягается. Данный словарь, например, используется поисковой системой www.yandex.ru.
Измерим частоту каждого слова текста. Некоторые слова будут иметь одинаковую частоту, то есть входить в текст равное количество раз. Сгруппируем их, взяв только одно значение из каждой группы. Расположим частоты по мере их убывания и пронумеруем. Порядковый номер частоты называется ранг частоты. Так, наиболее часто встречающиеся слова будут иметь ранг 1, следующие за ними - 2 и т.д. Теперь построим диаграмму частота - ранг.
Исследования показывают, что наиболее значимые слова лежат в средней части диаграммы. Это и понятно. Слова, которые встречаются слишком часто, в основном оказываются предлогами (в нашем случае предлог "из"). Редко встречающиеся слова тоже в большинстве случаев не имеют решающего смыслового значения.
От того, как будет выставлен диапазон значимых слов, зависит многое. Поставь широко - нужные термины потонут в море вспомогательных слов; установи узкий диапазон - потеряешь смысловые термины. Каждая поисковая система решает проблему по-своему.
Теперь проведем анализ выделенной нами области значимых слов (ранг и частота = 2). Не все слова из данной области будут выражать смысл текста. Точно выражать смысл абзаца будут слова "стаканчиков", "одноразовых", "водку" (их и выделит поисковая система в качестве терминов). Однако в область попали слова "не", "для", "в". Эти слова являются помехой, которые будут затруднять дальнейший выбор. Все эти слова рекомендуется предварительно исключить, используя специальный словарь "стоп-слов".
До сих пор мы рассматривали отдельно взятый документ (вернее небольшой его фрагмент), не принимая во внимание, что он входит в базу данных наряду с множеством других документов. Если представить всю базу данных как единый документ, к ней можно будет применить те же законы, что и к единичному документу. Посмотрите на список терминов в нашем примере. В одну компанию попали слова-термины и несколько предлогов - они входят в документ равное количество раз. Исследовав остальные документы базы данных на предмет вхождения в них этих терминов, мы обнаружим, что некоторые встречаются очень часто, другие - довольно редко. Напрашивается очевидный вывод: ключевые слова должны стать терминами, в то время как остальные следует отбросить, как помеху. Чтобы избавиться от лишних слов и в то же время поднять рейтинг значимых слов, вводят инверсную частоту термина. Значение этого параметра тем меньше, чем чаще слово встречается в документах базы данных. Вычисляют его по формуле:
Инверсная частота термина i = log (количество документов в базе данных / количество документов с термином i).
Теперь каждому термину можно присвоить весовой коэффициент, отражающий его значимость:
Вес термина i в документе j = частота термина i в документе j х инверсная частота термина i.
Наверняка в нашем примере термины-предлоги обязательно получат нулевой или близкий к нулю вес, поскольку практически во всех текстах их можно встретить. Ключевые термины, напротив, приобретут высокий вес.
Современные способы индексирования не ограничиваются анализом перечисленных параметров текста. Все много сложнее. Поисковая машина может строить весовые коэффициенты с учетом местоположения термина внутри документа, взаимного расположения терминов, частей речи, морфологических особенностей и т.п.
Итак, мы разобрались, как машина "понимает" суть текста. Теперь необходимо организовать всю коллекцию документов так, чтобы можно было легко отыскать в ней нужный материал. База данных должна взаимодействовать с пользовательским запросом. Запросы могут быть простыми, состоящими из одного слова, и сложными - из нескольких слов, связанных логическими операторами. Простой запрос оправдывает свое название. Пользователь вводит слово, машина ищет его в списке терминов и выдает все связанные с термином ссылки. Структура такой базы данных проста. Взаимодействие со сложными запросами требует более изощренной организации.
Наиболее простой способ представить элементы базы данных в форме, удобной для многовариантного поиска, - создать матрицу документ-термин. Предположим, база данных имеет 5 документов (Д1, ..., Д5), в которых содержатся 7 терминов. Если термин входит в документ, в соответствующей клеточке ставится единица, в противном случае - ноль (в реальной системе все сложнее: помимо прочего, учитываются еще и весовые коэффициенты терминов).
Составим, например, такой запрос: "похмелье от водки". Система обработает запрос: удалит стоп-слова (в данном случае предлог "от") и, возможно, проведет морфологический анализ. Останется два термина: "водка" и "похмелье". Система будет искать все документы, где встречается хотя бы один из терминов. Посмотрим на матрицу. Указанные в запросе термины есть в документах: Д1, Д2, Д3, Д4. Они и будут выданы в ответ на запрос. Кроме того, в документах Д1 и Д3 встречаются сразу оба термина, то есть ссылки на эти документы должны быть первыми в результатах поиска.
На практике поисковые системы используют пространственные модели представления документов базы данных. По результатам запроса поисковая система формирует вектор, в направлении которого и ведется поиск.
В реальности механизм индексации и структуры баз данных поисковых систем значительно сложнее. Однако полученных знаний вполне достаточно, чтобы попытаться выработать оптимальную стратегию поиска информации в сети Интернет либо подготовить документ для успешной индексации. Я, например, используя данную методику, подготовил для индексации сервер http://vodka.aga-va.ru (http://bestvodka.newmail.ru). В результате на запрос "похмелье" и Rambler, и Aport, и Yandex ссылку на сервер выдают в первом окне (это дает до 60 посетителей ежедневно только через поисковые машины). Ддя более детального ознакомления с методами работы поисковых систем советую посетить страницу http://dist-cons.ru/consulting/searchinf/spm/content5.html.
Андрей Скрыган
Возьмем в качестве примера следующий фрагмент текста: "Не пейте водку из одноразовых стаканчиков. В пластик, из которого изготавливают одноразовую посуду, для прочности добавляют стабилизаторы - полистирол и полипропилен. Поэтому ее многократное использование чревато серьезными последствиями для вашего здоровья. При взаимодействии, например, с алкоголем стаканчики из этих материалов начинают выделять отравляющие вещества, которые постепенно накапливаются в организме. Так что водку из одноразовых стаканчиков лучше не пить" (фрагмент текста взят со страницы http://vodka.agava.ru).
Теперь посчитаем количество вхождений каждого слова в данный фрагмент текста. Эта величина называется частотой вхождения слова. Процесс подсчета довольно трудоемок и скучен, поэтому рекомендую использовать специальный апплет (www.shipbottle.ru/ir), реализующий этот метод. Получился следующий результат (приведена статистика для слов с частотой больше 1):
4 - из
2 - стаканчиков
2 - одноразовых
2 - не
2 - для
2 - водку
2 - в
Данный апплет имеет существенный недостаток: частота каждого термина вычисляется без учета морфологии. Данную проблему легче всего решить, используя "Грамматический словарь русского языка", составленный Зализняком. Этот словарь очень хорошо отражает современное словоизменение, то есть для каждого входящего в словарь слова даны сведения о том, изменяемо ли оно, и если да, то как именно оно склоняется и спрягается. Данный словарь, например, используется поисковой системой www.yandex.ru.
Измерим частоту каждого слова текста. Некоторые слова будут иметь одинаковую частоту, то есть входить в текст равное количество раз. Сгруппируем их, взяв только одно значение из каждой группы. Расположим частоты по мере их убывания и пронумеруем. Порядковый номер частоты называется ранг частоты. Так, наиболее часто встречающиеся слова будут иметь ранг 1, следующие за ними - 2 и т.д. Теперь построим диаграмму частота - ранг.
Исследования показывают, что наиболее значимые слова лежат в средней части диаграммы. Это и понятно. Слова, которые встречаются слишком часто, в основном оказываются предлогами (в нашем случае предлог "из"). Редко встречающиеся слова тоже в большинстве случаев не имеют решающего смыслового значения.
От того, как будет выставлен диапазон значимых слов, зависит многое. Поставь широко - нужные термины потонут в море вспомогательных слов; установи узкий диапазон - потеряешь смысловые термины. Каждая поисковая система решает проблему по-своему.
Теперь проведем анализ выделенной нами области значимых слов (ранг и частота = 2). Не все слова из данной области будут выражать смысл текста. Точно выражать смысл абзаца будут слова "стаканчиков", "одноразовых", "водку" (их и выделит поисковая система в качестве терминов). Однако в область попали слова "не", "для", "в". Эти слова являются помехой, которые будут затруднять дальнейший выбор. Все эти слова рекомендуется предварительно исключить, используя специальный словарь "стоп-слов".
До сих пор мы рассматривали отдельно взятый документ (вернее небольшой его фрагмент), не принимая во внимание, что он входит в базу данных наряду с множеством других документов. Если представить всю базу данных как единый документ, к ней можно будет применить те же законы, что и к единичному документу. Посмотрите на список терминов в нашем примере. В одну компанию попали слова-термины и несколько предлогов - они входят в документ равное количество раз. Исследовав остальные документы базы данных на предмет вхождения в них этих терминов, мы обнаружим, что некоторые встречаются очень часто, другие - довольно редко. Напрашивается очевидный вывод: ключевые слова должны стать терминами, в то время как остальные следует отбросить, как помеху. Чтобы избавиться от лишних слов и в то же время поднять рейтинг значимых слов, вводят инверсную частоту термина. Значение этого параметра тем меньше, чем чаще слово встречается в документах базы данных. Вычисляют его по формуле:
Инверсная частота термина i = log (количество документов в базе данных / количество документов с термином i).
Теперь каждому термину можно присвоить весовой коэффициент, отражающий его значимость:
Вес термина i в документе j = частота термина i в документе j х инверсная частота термина i.
Наверняка в нашем примере термины-предлоги обязательно получат нулевой или близкий к нулю вес, поскольку практически во всех текстах их можно встретить. Ключевые термины, напротив, приобретут высокий вес.
Современные способы индексирования не ограничиваются анализом перечисленных параметров текста. Все много сложнее. Поисковая машина может строить весовые коэффициенты с учетом местоположения термина внутри документа, взаимного расположения терминов, частей речи, морфологических особенностей и т.п.
Итак, мы разобрались, как машина "понимает" суть текста. Теперь необходимо организовать всю коллекцию документов так, чтобы можно было легко отыскать в ней нужный материал. База данных должна взаимодействовать с пользовательским запросом. Запросы могут быть простыми, состоящими из одного слова, и сложными - из нескольких слов, связанных логическими операторами. Простой запрос оправдывает свое название. Пользователь вводит слово, машина ищет его в списке терминов и выдает все связанные с термином ссылки. Структура такой базы данных проста. Взаимодействие со сложными запросами требует более изощренной организации.
Наиболее простой способ представить элементы базы данных в форме, удобной для многовариантного поиска, - создать матрицу документ-термин. Предположим, база данных имеет 5 документов (Д1, ..., Д5), в которых содержатся 7 терминов. Если термин входит в документ, в соответствующей клеточке ставится единица, в противном случае - ноль (в реальной системе все сложнее: помимо прочего, учитываются еще и весовые коэффициенты терминов).
Составим, например, такой запрос: "похмелье от водки". Система обработает запрос: удалит стоп-слова (в данном случае предлог "от") и, возможно, проведет морфологический анализ. Останется два термина: "водка" и "похмелье". Система будет искать все документы, где встречается хотя бы один из терминов. Посмотрим на матрицу. Указанные в запросе термины есть в документах: Д1, Д2, Д3, Д4. Они и будут выданы в ответ на запрос. Кроме того, в документах Д1 и Д3 встречаются сразу оба термина, то есть ссылки на эти документы должны быть первыми в результатах поиска.
| Д1 | Д2 | Д3 | Д4 | Д5 | |
| Водка | 1 | 1 | 1 | 0 | 0 |
| Стакан | 1 | 1 | 0 | 1 | 0 |
| Вино | 0 | 1 | 0 | 1 | 0 |
| Похмелье | 1 | 0 | 1 | 1 | 0 |
| Игра | 1 | 0 | 0 | 0 | 1 |
| Лекарство | 1 | 0 | 0 | 1 | 1 |
| Закуска | 1 | 1 | 1 | 0 | 0 |
В реальности механизм индексации и структуры баз данных поисковых систем значительно сложнее. Однако полученных знаний вполне достаточно, чтобы попытаться выработать оптимальную стратегию поиска информации в сети Интернет либо подготовить документ для успешной индексации. Я, например, используя данную методику, подготовил для индексации сервер http://vodka.aga-va.ru (http://bestvodka.newmail.ru). В результате на запрос "похмелье" и Rambler, и Aport, и Yandex ссылку на сервер выдают в первом окне (это дает до 60 посетителей ежедневно только через поисковые машины). Ддя более детального ознакомления с методами работы поисковых систем советую посетить страницу http://dist-cons.ru/consulting/searchinf/spm/content5.html.
Андрей Скрыган
Компьютерная газета. Статья была опубликована в номере 02 за 2000 год в рубрике интернет :: разное
