Анализ текстовых докуметов. Получение ключевых слов.

Появилась интересная задачка по вычленению ключевых слов из текстового документа. Необходимо разработать такой модуль, который на входе получает текстовой файл, а на выходе выдает ключевые слова которые могли бы дать представление о чем идет речь в документе, с помощью ключевых слов.

К примеру, есть статья о хокейном матче между динамо рига - динамо москва, ключевыми словами должны быть: хоккей, динамо рига, динамо москва, матч, чемпионат.

Существует несколько алгоритмов, основанных на алгоритмах обработки естественного языка, но они довольно сложные и не укладываются в временные рамки. К тому же алгоритмы для каждого языка отличаются.

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

Алгоритм включает следующие шаги:

0. Определение языка

1. Stemming, на основании алгоритма Потера

2. Построение frequency таблицы

3. Кластеризация часты термов

4. Вычисление совстречаемости термов

5. Вычисление хи-квадрата для термов

6. Выбор терма с наибольшим значением хи-квадрата - это и будет ключевое слово


Далее каждый шаг рассматривается детально.

0. Для определения языка можно поставить гем: whatlanguage. Работает он предельно просто:
>> "Je suis un homme".language
=> :french

1. Для стеминга существует несколько алгоритвом реализованных в руби
* Номер раз
* Номер два

Второй вариант написан на C и автор утверждает что он быстрее. Использовать это очень просто:

$ script/console
=> 'running'.stem
>> 'run'

2. Построение таблицы частот

Тут я реализовал простенький алгоритм, в дальнейшем его планирую переписать на с:


class FrequencyHash < Hash
  
  def occur(key)
    if include?(key)
      store(key, self[key] + 1)
    else
      store(key, 1)
    end
  end
  
  def frequent_keys(min_frequency)
    self.keys.reject{|key| self[key] < min_frequency}.sort{|a,b| self[b] <=> self[a] && a <=> b}
  end
  
end

require 'stemmer'
require 'whatlanguage'

module KeywordsHelper
  MIN_LENGHT = 3
  
  def get_frequences(full_text)  
    words = FrequencyHash.new
    full_text.split(/\W/).each do |word|
      word = word.stem
      words.occur(word) if word.length >= MIN_LENGHT
    end
    words.frequent_keys(2)
  end
  
end


Далее переходим к шагу 3...

To be continued...
Ярлыки: , , , , ,