Skip to content
Tags

,

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

18/08/2009

Когда то давно я прочитал статью какого то работника 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 довольно плохо — мне просто хотелось посмотреть будет ли решение достаточно красивым в сравнении с обычными алгоритмами подсчёта количества слов 🙂

Реклама
3 комментария
  1. Fedya permalink

    код не работает 😦 почему-то не могу его никак запустить
    array(1) { [«»]=> int(1) }
    вот что выводит.

    • kuroikaze85 permalink

      Надо смотреть в лог. Возможно дело в версии PHP — я не в курсе насчёт закидонов map/reduce в предыдущих версиях, но вполне допускаю.

  2. serg permalink

    О, крутая функция, спс:)
    у меня заработала после этого:
    $text = ‘Matthew Boulton (1728–1809) was … evolution.’;

    /*этот кусок _после_ объявления $text, его ж делим на слова))*/
    $splitters = ‘-\s.,\(\)?:;’; // string splitters
    $array = preg_split( «/[» . $splitters . «]*\\\»([^\\\»]+)\\\»[» . $splitters . «]*|[» . $splitters . «]+/», $text, 0, PREG_SPLIT_DELIM_CAPTURE );
    /*этот кусок _после_ объявления $text*/

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

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

Заполните поля или щелкните по значку, чтобы оставить свой комментарий:

Логотип WordPress.com

Для комментария используется ваша учётная запись WordPress.com. Выход / Изменить )

Фотография Twitter

Для комментария используется ваша учётная запись Twitter. Выход / Изменить )

Фотография Facebook

Для комментария используется ваша учётная запись Facebook. Выход / Изменить )

Google+ photo

Для комментария используется ваша учётная запись Google+. Выход / Изменить )

Connecting to %s

%d такие блоггеры, как: