Подсветка естественного языка

Идея такой подсветки у меня возникла в связи с законопроектом о приравнивании компьютерных языков иностранным 416D65726963612043616E20436F646520, рассмотренным конгрессом США в декабре 2013. Использование подсветки синтаксиса при создании программ уже давно принятая практика, но вопрос подсветки естественных языков на момент написания этого материала ограничивался парой коротких обсуждений на англоязычных форумах. Тем не менее, если можно облегчить визуальное восприятие текста путём автоматического выделения некоторых слов почему бы не попробовать.

Компьютерные языки безусловно отличаются строгостью, конструкции обычно подсвечиваются в соответствии с выполняемой функцией (оператор, число, строка и т. д. ) и первой идеей, которая приходит в голову является аналогичная подсветка естественных текстов (подлежащее, сказуемое и т.д.) В качестве примера рассмотрим начало “Фантастического рассказа” Ф. М. Достоевского, выделим все подлежащие зелёным цветом, а сказуемые — синим:



Подобная разметка требует довольно сложного анализа текста, но на мой взгляд подсветка не должна быть сложной (скорость работы алгоритма подсветки должна быть примерно того же порядка, что и скорость загрузки страницы), чтобы ею можно было комфортно пользоваться. Я решил остановиться на более простом варианте, а именно, на подсветке частотности, базируясь на идее, что чем чаще повторяется слово, тем меньше смысла оно несёт. Строго говоря, это конечно не верно, но если разметить уже указанный отрывок Достоевского, отмечая полужирным те слова, которые далее не используются в рассказе — получится следующее:



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

Для начала напишем функцию, которая по заданному регулярному выражению обновляет словарь частотности слов:

function collect(text, frequences, pattern) {
   var words = text.split(/\s+/); //  разбиваем по словам
   for (var j = 0; j < words.length; j++) {
         // каждое слово переводим в нижний регистр и убираем все неинтересные символы
	 var current = words[j].toLowerCase().replace(pattern,'');
         // также исключаем слишком короткие слова
	 if (!current || current.length < MIN_LENGTH) continue;
         // если слово отсутствует в частотном словаре -- добавляем его, если нет -- увеличиваем счётчик
	 if (!frequences[current]) frequences[current] = 1;
	 else frequences[current] += 1;
   }
}

Соберём статистику использования слов из DOM:

var pattern = /[^а-яё]/g
var freq = {}
function stat(element) {
	if (/(script|style)/i.test(element.tagName)) return; // не заходим внутрь стилей и скриптов
	if (element.nodeType === Node.ELEMENT_NODE && element.childNodes.length > 0)
		for (var i = 0; i < element.childNodes.length; i++)
			stat(element.childNodes[i]);
	
        // для непустых текстовых элементов вызываем collect
	if (element.nodeType === Node.TEXT_NODE && (/\S/.test(element.nodeValue))) { 
	   collect(element.nodeValue, freq, pattern);
  }
}

stat(window.document.getElementsByTagName('html')[0]);

Затем, исключим из статистики те слова, которые встречаются чаще, чем нам это нужно:

function remove(o, max) {
	var n = {};
	for (var key in o) if (o[key] <= max) n[key] = o[key];
	return n;
}
freq = remove(freq, maxFreq);

И наконец подсветим все вхождения интересных нам слов:

function markup(element, pattern) {
	if (/(script|style)/i.test(element.tagName)) return; // здесь также не заходим внутрь стилей и подпрограмм
	if (element.nodeType === Node.ELEMENT_NODE && element.childNodes.length > 0) {
		// для всех элементов, считаем частотность для элементов-потомков, чтобы не пытаться заменить то, чего нет
		var freq = {};
		for (var i = 0; i < element.childNodes.length; i++) 
			if (element.childNodes[i].nodeType === Node.TEXT_NODE && (/\S/.test(element.childNodes[i].nodeValue)))
                    collect(element.childNodes[i].nodeValue, freq, pattern);
					
		if (freq && freq.length !== 0) {
			var efreq = [];
			var total = 0;
			// оставляем только те слова, которые есть в глобальном словаре
			// сохраняем их в виде пар [слово, частотность] с тем, чтобы можно было потом отсортировать по длине
			// сортировка нужна для того, чтобы замена подслов не отменяла замены слова
			for (var key in freq) if (freqRus[key]) efreq.push([key, freq[key]]);
			efreq.sort(function(a, b) {return a[0].length - b[0].length});
			// на всякий случай ограничиваем количество итераций цикла, поскольку мы добавляем ноды-потомки,
			// а это может вызвать постоянное увеличение длины и бесконечный цикл
			var max = element.childNodes.length*efreq.length*2;
			for (var i = 0; i < element.childNodes.length; i++) {
				if (total++ > max) break;
				if (element.childNodes[i].nodeType === Node.TEXT_NODE) {
					var minPos = -1, minJ = -1;					
					// в каждом отдельном текстовом элементе ищем первое вхождение одного из интересных нам термов
					for (var j in efreq) {
						key = efreq[j][0];
						var pos = element.childNodes[i].nodeValue.toLowerCase().indexOf(key);
						if (pos >= 0 && (minJ === -1 || minPos>pos)) { minPos = pos; minJ = j; }
					}
					// и если таковой нашёлся -- заменяем его
					if (minPos !== -1) {
						key = efreq[minJ][0]; val = efreq[minJ][1];
						// сначала разбиваем текст на начало, середину и конец, а потом заменяем середину тегом "strong"
						var spannode = window.document.createElement('strong');
						var middle = element.childNodes[i].splitText(minPos);
						var endbit = middle.splitText(key.length);
						var middleclone = middle.cloneNode(true);
						spannode.appendChild(middleclone);
						element.replaceChild(spannode, middle);
					}
				}
			}
		}
	}	
   }
}
markup(window.document.getElementsByTagName('html')[0], pattern);

Заключение

Хорошо бы учитывать словоформы и возможно копить историю (то есть работать не в рамках одной страницы, а строить словарь частотности собирая всё вместе). Кроме того хорошо бы иметь возможность влиять на словарь (фиксировать там какие-нибудь слова, а какие-нибудь никогда не включать).

Полностью приведённые примеры можно взять с github:
github.com/parsifal-47/nalacol

или сразу в виде приложения для Chrome:
chrome.google.com/webstore/detail/natural-language-colorer/jjcldlhpnolppcclcgdbblbilmealfjd

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