Подсчёт количества вхождений слов с помощью map/reduce.

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

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

Что это нам даёт? В PHP есть функции array_map и array_reduce. Логично было бы попробовать реализовать этот же алгоритм в PHP 🙂

Как, вообще говоря, работает эта программа? Во первых, куски текста прогоняются через функцию-преобразователь. Это шаг map. Функция-преобразователь приводит слова к нормальной форме и возвращает хеш-таблицу следующего вида:

$result = array(
    'слово1' => 1,
    'слово2' => 1,
    'слово3' => 1,
    'слово4' => 1,
    ...
);

где слово1..слово4 — нормальные формы слов (после стемминга).

На втором шаге к полученным хеш-таблицам попарно применяется функция свёртки (reduce), возвращающая такую же таблицу. Это происходит до тех пор пока не останется один результат. Функция свёртки просто «складывает» две хеш-таблицы — полученную из шага map и таблицу-аккумулятор —, суммируя значения если ключ присутствует в обеих начальных таблицах.

Зачем вообще нужны эти сложности? Дело в том что все операции map и большинство операций reduce независимы друг от друга. Можно разделить огромный текст на 1000 кусков и провести map-преобразование всех кусков одновременно на кластере. Reduce также можно довольно эффективно распараллелить.

Главная засада в PHP-реализации свёртки — это то что начальным значением аккумулятора может быть только Integer. Хорошая новость — функция свёртки может назначить аккумулятору любой тип, и аккумулятор будет без проблем передаваться дальше. Итак, сам код:

	function lcount($string) {
		return array($string => 1);
	}

	function rcount($w1, $w2) {
		if (!is_array($w1)) {
			$w1 = array();
		}
		foreach ($w2 as $word => $count) {
			$w1[$word] += $count;
		}
		return $w1;
	}

	$splitters = '-\s.,\(\)?:;'; // string splitters
	$array = preg_split( "/[" . $splitters . "]*\\\"([^\\\"]+)\\\"[" . $splitters . "]*|[" . $splitters . "]+/", $str, 0, PREG_SPLIT_DELIM_CAPTURE );

	$text = 'Matthew Boulton (1728–1809) was an English manufacturer and the partner of engineer James Watt. In the final quarter of the 18th century, the partnership installed hundreds of Boulton & Watt steam engines, which were a great advance on the state of the art, making possible the mechanisation of factories and mills. He became associated with James Watt when Watt\'s business partner, John Roebuck, was unable to pay a debt to Boulton, who accepted Roebuck\'s share of Watt\'s patent as settlement. He then successfully lobbied Parliament to extend Watt\'s patent for an additional seventeen years, enabling the firm to market Watt\'s steam engine. Boulton applied modern techniques to the minting of coins, striking millions of pieces for Britain and other countries, and supplying the Royal Mint with up-to-date equipment. Boulton was a key member of the Lunar Society, a group of Birmingham-area men prominent in the arts, sciences, and theology. Members included Boulton, Watt, Erasmus Darwin, Josiah Wedgwood, and Joseph Priestley. Members of the Society have been given credit for developing concepts and techniques in science, agriculture, manufacturing, mining, and transportation that laid the groundwork for the Industrial Revolution and for later discoveries, including the theory of evolution.';

	$result = array_reduce(array_map('lcount', array_map('strtolower', $array)), 'rcount');

	$words = array_flip(array(
		'the',
		'of',
		'and',
		'to',
		'for',
		'a',
		'was',
		'in',
		'an',
		'He',
		'but'
	));

	$result = array_diff_key($result, $words);

	arsort($result);
	var_dump($result);

В принципе функцию lcount можно определить и однострочником прямо в array_map — при помощи create_function, т.к. у нас текст разбивается не на абзацы, например, а на слова. Также не используется стемминг. В конце выкидываются наиболее часто используемые слова — это было частью начальной задачи на StackOverflow, по мотивам которой и написан скрипт. Я в курсе что с параллелизмом в PHP довольно плохо — мне просто хотелось посмотреть будет ли решение достаточно красивым в сравнении с обычными алгоритмами подсчёта количества слов 🙂