Май 2018 — ИТ-заметки

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

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

Одновременно с подсчётом частоты вхождения мы вычисляем максимальную частоту вхождения слов в текст, а также сколько слов имеют эту частоту.
Поскольку приведённая схема не привязана к какому-либо языку программирования, в блоках проверки условий используется обычное «=» из математики. При реализации алгоритма на конкретном языке программирования важно заменить его на оператор сравнения, который используется в этом языке. В 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 представлен скриншот работы программы у меня. Программа работает именно так как ожидалось.

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

Получение курсов валют — задача, которая встречается очень часто. Курсы могут понадобиться чтобы просто показать их на веб-странице. Другой не менее распространённый случай — необходимость пересчитать цену в разных валютах. Какой бы ни была цель, важно чтобы курсы были получены из надёжного источника. Не менее важна их актуальность.

Самый надёжный и актуальный источник курсов валют — сайт Центробанка РФ. Через него можно получить доступ к XML-документу с курсами. Для этого нужно обратиться по URL ‘http://www.cbr.ru/scripts/XML_daily.asp’. В документе будет курсы валют на текущую дату. Также можно добавить к адресу параметр date_req, который позволяет явно указать дату, на которую нужны курсы. Тогда URL будет выглядеть следующим образом: ‘http://www.cbr.ru/scripts/XML_daily.asp?date_req=d.m.Y’. d.m.Y — это формат даты: день.месяц.год.
Кстати, PHP прекрасно понимает такие форматы дат.
XML-документ с курсами валют имеет следующую структуру: внутри корневого элемента находятся тэги <Valute>. Внутри каждого такого тэга находятся тэги, содержащие информацию о конкретной валюте. Для примера приведу скриншот XML-документа:

Тэгов внутри каждого элемента <Valute> довольно много, но чаще всего нужны 2 — <CharCode> и <Value>. С первым всё понятно, а второй — это курс валюты к рублю.
Таким образом, чтобы получить нужную нам информацию, надо сначала получить из PHP доступ к корневому XML-элементу, а потом перебрать все вложенные в него элементы <Valute>. Для каждого из них нужно просмотреть содержимое тех тэгов, которые описывают нужные нам свойства валюты.
Получить доступ ко вложенным XML-элементам из PHP совсем не сложно. Элементы можно получить по названию тэга с помощью функции getElementsByTagName(). Она возвращает коллекцию подходящих элементов. Для элементов <Valute> надо просто перебрать эту коллекцию в цикле, как уже говорилось выше. Когда мы ищем элементы, хранящие свойтва наподобие <CharCode>, внутри элемента <Valute>, функция getElementsByTagName() вернёт коллекцию из одного элемента. К нему можно обратиться следущим образом: item(0). Текст внутри тегов XML-элемента хранит свойство объекта nodeValue.
Теперь рассмотрим код примера на PHP:

<html>
<?php
//Xml-документ с курсами валют к рублю с сайта ЦБ РФ
$xml = new DOMDocument();
$url = 'http://www.cbr.ru/scripts/XML_daily.asp?date_req=' . date('d.m.Y');

//Пробуем скопировать xml-документ с курсами валют с сайта ЦБ РФ на наш сервер
$local_exchange_rates = "exchange_rates.xml";
@copy($url, $local_exchange_rates);

//Поддерживаемые валюты и их курс к рублю
$supported_currencies = ['USD' => NULL, 'EUR' => NULL];

//Загружаем xml-документ с курсами
$is_loaded = false;
if (@$xml->load($url))
  $is_loaded = true;
elseif (@$xml->load($local_exchange_rates))
  $is_loaded = true;

//Обновляем курсы поддерживаемых валют
if ($is_loaded)
{
  $root = $xml->documentElement;
  $currencies = $root->getElementsByTagName('Valute');
  foreach ($currencies as $currency)
  {
    $char_code = $currency->getElementsByTagName('CharCode')->item(0)->nodeValue;
    if (array_key_exists($char_code, $supported_currencies))
    {
      $value = $currency->getElementsByTagName('Value')->item(0)->nodeValue;
      $supported_currencies[$char_code] = floatval(str_replace(',', '.', $value));
    }
  }
  foreach ($supported_currencies as $key => $value)
  {
    echo $key.' '.$value.'<br>';
  }
}
else
  echo "Не удалось загрузить курсы валют";
?>
</html>

Стоит обратить внимание на 2 вещи:

Мы выводим курсы только для тех валют, которые отметили как поддерживаемые. Для этого мы объявили массив $supported_currencies и поместили туда буквенные коды тех валют, которые хотим отслеживать.
При каждом обращении к сайту ЦБ РФ мы сохраняем копию XML-документа локально. Если при следующем обращении к сайту ЦБ РФ он будет недоступен, то мы возьмём данные из локальной копии.
Рисунок 2

Эта система очень проста, но далеко не идеальна. Если предыдущее обращение было давно, то пользователь получит неактуальные курсы валют. Более сложный, но и более надёжный способ — вынести код создания локальной копии в отдельную программу и запускать эту программу как задание с определённой периодичностью. Но в этом посте мы не будем рассматривать как это сделать.

Месяц: Май 2018

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

Получение курсов валют