Подсчёт частоты вхождения слов в текст

Сегодня я покажу как написать программу на языке высокого уровня, которая подсчитывает частоту вхождения слов в текст. Для этого воспользуемся языком Ruby. Он очень хорошо подходит для работы с текстом.
Идея программы очень проста. Мы хотим определить сколько раз каждое слово встречается в тексте. Для этого прежде всего нужно определиться со структурой данных, в которую мы будем записывать результаты вычислений. Лучше всего, если не придётся создавать временных контейнеров в оперативной памяти для промежуточных вычислений. То есть промежуточные результаты и результат финальный должны храниться в одном месте и в одинаковом виде. Во всех современных языках программирования есть структуры данных, которые позволяют хранить данные в формате «ключ»-«значение». И «ключ», и «значение» могут быть любого типа. Во многих языках программирования такие структуры данных называются ассоциативными массивами (например, в PHP). В Ruby они называются хэшами. Такая структура данных лучше всего подходит для наших целей. Ключом будет являться слово, а значением — количество его вхождений в текст. Когда программа будет находить в тексте новое слово, в хэш будет добавляться новая пара «ключ»-«значение». А если программа встречает в тексте слово, которое уже добавлено в хэш, то нужно всего лишь прибавить 1 к «значению» соответствующего ключа. Описанная структура данных схематически изображена на рисунке 1.

Рисунок 1

Теперь, когда мы определились со структурой данных, нужно подумать об алгоритме. Думаю, что проще всего сразу же показать блок-схему. На ней все шаги алгоритма показаны подробно и без привязки к Ruby или какому-либо языку программирования.

Рисунок 2

Одновременно с подсчётом частоты вхождения мы вычисляем максимальную частоту вхождения слов в текст, а также сколько слов имеют эту частоту.
Поскольку приведённая схема не привязана к какому-либо языку программирования, в блоках проверки условий используется обычное «=» из математики. При реализации алгоритма на конкретном языке программирования важно заменить его на оператор сравнения, который используется в этом языке. В Ruby используется C-подобная форма оператора сравнения: «==». А «=» обозначает оператор присваивания.
Вот код программы на Ruby, которая реализует этот алгоритм:

begin
  frequency_table=Hash.new

  puts 'Enter name of the file:'
  file_name = gets.chomp!
  data = IO.read(file_name)
  words=data.scan(/[A-Za-z]+(?:'s)?/)

  words.each do |word|
    if (frequency_table.include? word.downcase) then
      frequency_table[word.downcase]+=1
    else
      frequency_table.[]=(word.downcase,1)
    end
  end
  max_word_len=0
  counter=0
  puts "Only words more frequent than 'limit' will be shown. Enter 'limit':"
  limit = gets.to_i
  frequency_table.each do |key, value|
    if value>max_word_len then
      max_word_len=value
      counter=1 #Начинаем подсчёт заново
    else
      if value==max_word_len then
        counter+=1
      end
    end
    if (value > limit) then print "#{key}: #{value}\n" end
  end
  puts "The highest frequency is #{max_word_len}. Words which have this frequency repeats in text #{counter} times."
  gets
rescue=>err
  puts err
  gets
end

Программа полностью соответствует алгоритму, приведённому выше. Отдельно стоит остановится только на регулярном выражении «[A-Za-z]+(?:'s)?». Оно находит последовательности из букв английского алфавита, в которые не вклиниваются другие символы. Регулярное выражение учитывает, что слова могут заканчиваться на «’s». Это позволяет распознавать прилагательные, которые в английском языке обозначают принадлежность. Важно использовать группировку без запоминания: «(?: )». При использовании обычной группировки «( )» метод scan будет работать совсем не так, как ожидается. Не вдаваясь в подробности, скажу, что он не будет искать соответствия регулярному выражению в тексте.
Проверим программу на текстовом файле. Я для этих целей использовал специально созданный файл example.txt. Объём текста в нём совсем небольшой, и работу программы легко можно проверить вручную. У меня содержимое этого файла следующее: «Girl are playing with her dog. … Dog’s name is Snuppy. Girl’s nAme is Katty.». Я внёс в текст некоторые искажения специально, чтобы проверить, как программа с ними справится. На рисунке 3 представлен скриншот работы программы у меня. Программа работает именно так как ожидалось.

Рисунок 3

Чтобы запустить эту программу и опробовать её у себя нужен только установленный интерпретатор Ruby.
Программа, которую мы сегодня рассмотрели, разумеется, очень проста. В частности, она не учитывает морфологию. Разные формы одного слова программа считает разными словами. В следующих постах я покажу как можно её усовершенствовать. Заодно рассмотрим на примере этой программы некоторые полезные приёмы и инструменты для работы с текстами.

Подсчёт частоты вхождения слов в текст: 9 комментариев

  1. Мне вообще всю жизнь слово «приложение» (в компьютерном смысле) казалось странным. Аппликация — рисунок, получаемый приклеиванием кусочков цветной бумаги. Приложение ассоциируется либо с дополнительными главами в конце книги, либо с какими-то припарками, перцовыми пластырями. Зачем ПО прикладывать к компьютеру?

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *