АВТОМАТИЗИРОВАННОЕ ПОСТРОЕНИЕ СПИСКОВ СЕМАНТИЧЕСКИ БЛИЗКИХ СЛОВ

АВТОМАТИЗИРОВАННОЕ ПОСТРОЕНИЕ СПИСКОВ СЕМАНТИЧЕСКИ БЛИЗКИХ СЛОВ НА ОСНОВЕ РЕЙТИНГА ТЕКСТОВ В КОРПУСЕ С ГИПЕРССЫЛКАМИ И КАТЕГОРИЯМИ

А.А. Крижановский
Санкт-Петербургский институт информатики и автоматизации РАН
/ aka at iias dot spb dot su /

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

(1)

(2)

(4)

(5)

Предобработка

(две косые черты '//' отделяют комментарий от псевдокода)

Построить кластеры (массив Clusters) по категориям: изначально каждый кластер соответствует отдельной вершине (категории). Приписать каждому кластеру (за счёт содержащихся в кластере категорий):

|с _articles| = число статей, которые ссылаются на категории в кластере,
c _weight = 1 + |с _articles| // изначально вес кластера – это число категорий в кластере (изначально одна категория) и число статей, которые ссылаются на эту одну категорию,
c _{category_id}[0] = category _id // присваиваем кластеру уникальный идентификатор id первой (и единственной пока) категории, добавленной в кластер (у каждой категории и статьи Википедиа есть уникальный идентификатор).

Для каждого ребра между категориями создать ребро между кластерами. Каждому ребру e, соединяющему два кластера c1 и c2 определить вес так:

e _weight = c1 _weight + c2 _weight

Алгоритм

E _sorted = sort(e _weight); // сортировка рёбер по весу
while(|E _sorted| > 0 && (E _sorted [0] < MaxClusterWeight)) BEGIN
e = E _sorted[0]; // v₁, v₂ – вершины смежные ребру e
E _sorted = E _sorted \ Г(v₂); // удалить из упорядоченного массива рёбер рёбра смежные v₂
merge(e); // объединить вершины-кластеры v₁ и v₂ в кластер v₁, т.е. добавить вершину v₂ в кластер v₁, изменив свойства v₁ так:
1. v_1
  weight += v_{2 weight}; // увеличить размер кластера (число категорий и статей)
2. |v_{1
  articles}| += |v_{2 articles}|; // увеличить число статей
3. |v_1
  edges| += |v_{2 edges}|; // увеличить число рёбер
4. v₁ _{category_id}[] += addUnique(v_{2 category_id}[]); // добавили категории без повторов
passEdges(); // все рёбра смежные вершине v₂ передать вершине v₁ (рёбра без повторений, это не мультиграф).
Esorted = Esorted \ edge (v₁, v₂); // удалить ребро (v₁, v₂);
updateEdgesOfMergedCluster; // обновить указатели на вершины, удалить ребра (вершины и рёбра, смежные удаляемой вершине)
updateEdgeWeight(v₁); // пересчитать значения весов для всех рёбер смежных v₁
remove(Clusters, v₂); // удалить кластер v₂ из массива кластеров
E _sorted = sort(e _weight) // пересортировка рёбер, сложность O(N), т.к. нужно обновить порядок только тех рёбер, которые смежны вершине v₁
END
Return Clusters