Теория

pva · Отправлено: **20:51, 10-11-2013** | #2

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

Код:

#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
#include <functional>
#include <numeric>
#include <list>
#include <valarray>
using namespace std;

template<typename Iterator2, typename Iterator1, typename OutputIterator,
	typename Value, typename Plus, typename Times>
void corelate(Iterator2 sample_first, Iterator2 sample_last, Iterator1 data_first,
		OutputIterator result_first, OutputIterator result_last,
		Value init, Plus plus, Times times)
{
	for(; result_first!=result_last; ++data_first,++result_first) {
		*result_first = inner_product(sample_first, sample_last, data_first, init, plus, times);
	}
}

template<typename T>
unsigned fuzzy_match(T const& a, T const& b) {
	return a==b ? 100 : 0;
}

template<>
unsigned fuzzy_match(string const& a, string const& b) {
	string::size_type a_size=a.size(), b_size=b.size();
	plus<unsigned> plus;
	unsigned accum;

	if (a_size && b_size) {
		switch(a_size-b_size) {
		case 0:
			accum = inner_product(a.begin(), a.end(), b.begin(),
						unsigned(), plus, fuzzy_match<string::value_type>)
				+ inner_product(b.begin()+1, b.end(), a.begin(),
						unsigned(), plus, fuzzy_match<string::value_type>)
				+ inner_product(a.begin()+1, a.end(), b.begin(),
						unsigned(), plus, fuzzy_match<string::value_type>);
			break;

		case 1:
			accum = inner_product(b.begin(), b.end(), a.begin(),
						unsigned(), plus, fuzzy_match<string::value_type>)
				+ inner_product(b.begin(), b.end(), a.begin()+1,
						unsigned(), plus, fuzzy_match<string::value_type>);
			break;

		case ~0u:
			accum = inner_product(a.begin(), a.end(), b.begin(),
						unsigned(), plus, fuzzy_match<string::value_type>)
				+ inner_product(a.begin(), a.end(), b.begin()+1,
						unsigned(), plus, fuzzy_match<string::value_type>);
			break;

		default:
			return 0;
		}

		return 2*accum / (a_size + b_size);
	}
	return 0;
}

template<typename T>
unsigned fuzzy_search(list<T> const& sample, list<T> const& source,
		valarray<unsigned> &match,
		unsigned spread_size, unsigned const *spread_sensitivity)
{
	typename list<T>::size_type sample_size=sample.size(), source_size=source.size();

	if (source_size >= sample_size + spread_size) {
		match.resize(source_size - sample_size);
		unsigned *r1 = &match[0], *r2 = &match[match.size()];

		corelate(sample.begin(), sample.end(), source.begin(), r1, r2,
				unsigned(), plus<unsigned>(), fuzzy_match<T>);

		corelate(spread_sensitivity+0, spread_sensitivity+spread_size, r1, r1, r2-spread_size,
				unsigned(), plus<unsigned>(), multiplies<unsigned>());

		return match.max();
	}
	return 0;
}

void load_words(const char *name, list<string>& result) {
	filebuf in;
	in.open(name, ios_base::in);
	string word;
	int c = in.sbumpc();
	for (; c!=-1; c=in.sbumpc()) {
		if (192<=c || isalpha(c)) {
			word.clear();
			do { word.push_back(c|32), c=in.sbumpc(); }
			while (192<=c || isalpha(c));
			result.push_back(word);
		}
	}
}

int main() {
	static unsigned const spread_size = 1;
	static unsigned const accept_percent = 90;
	static unsigned const spread[] = {1,1,1,1,1,1,1,1};

	list<string> sample, text;
	valarray<unsigned> match;
	unsigned threshold;

	load_words("sample.txt", sample);
	load_words("text.txt", text);
	threshold = accept_percent*fuzzy_search(sample, text, match, spread_size, spread)/100;

	unsigned sample_size = sample.size();
	unsigned match_pos = 0;
	list<string>::iterator pos = text.begin();
	for(; match_pos!=match.size(); ++match_pos,++pos) {
		if (threshold < match[match_pos]) {
			list<string>::iterator word = pos;
			cout << match[match_pos]/sample_size << "%:";
			for(unsigned n=sample_size; n; ++word,--n) {
				cout << " " << *word;
			}
			cout << "\n";
		}
	}

	return 0;
}

можно играться spread_size, коэффициентами spread (будет сдвигаться ответ)
ответ получается понятней, когда spread_size = 1
исходный файл - text.txt
что искать - sample.txt
понимает английские и русские буквы в 1251

pva · Отправлено: **11:48, 12-11-2013** | #3

В общем, придумал способ находить цитаты (и подписи, если считать их цитатами), второе приближение.

Задача №1: найти все репосты. Решение: ищем общую последовательность максимальной длины, помечаем, вырезаем, разделяем найденной частью один из списков на два. Для каждой получившихся частей повторяем задачу заново.

Задача №2: в 2-х списках строк найти общую последовательность максимальной длины. Решаем как задачу динамического программирования. Пусть список sample - тот, из которого ищем цитаты, text - тот в котором ищем. Управление: позиция в sample, с которой начинается цитата. Состояние: лучшая длина + начало цитаты, текущая длина.
Т.о. возможен однопроходной алгоритм, количество сравнений - N*M, где N и M - длины списков.
Если считать цитаты достаточно редкими, то можно уменьшить расходуемую память и ускорить обработку за счёт использования хеш-мапов строк на состояния.

Если требуется нечёткое сравнение, то строки предварительно обрабатываются канонанизатором (т.е. перекодируются, выкидываются части, не имеющие значения)

Вероятно можно переформулировать задачу так, чтобы на выходе сразу получался разбитый цитатами список.

Какие ещё могут быть варианты решения задачи?

XPEHOMETP · Отправлено: **14:59, 12-11-2013** | #4

Цитата pva:

2. Выделить цитаты и ответы на них (если есть) »

Зависит от почтового сервера, как я подозреваю. На моем они (цитаты) в начале строки помечены знаком >. Причем я совсем не гарантирую, что те же самые фишки сохранятся при смене сервера. Но, тем не менее, ежели в начале цитаты есть некий определенный знак (совсем даже редкий для обычного e-mail сообщения), то запрограммировать обнаружение подобных цитат - это раз плюнуть.

pva · Отправлено: **11:37, 13-11-2013** | #5

Честно говоря, я думал что значки ">>" проставляет почтовый клиент. В письмах, которые я взял для анализа, я обнаружил кроме html-ных частей ещё текстовые копии (для старых почтовых клиентов), там такие значки проставляются. Но не со всеми письмами прокатывает.

В общем, я провёл эксперименты со вторым приближением. За образец взял два "очень длинных письма" - два рассказа братьев Стругацких, с разделением по словам, а не по строкам, у слов отрезаются окончания (такой канонизатор). Время измеряно для отладочной сборки.

Код:

longest match (10): библиотек ладошек http palm com ладошк солнц карманны компьютеры аркад
sample 72835 words
text 40581 words
took 120 secs

2 минуты - плохо, но лучше, чем поиск каждой подстроки sample в text (его я так и не дождался ща полчаса).

Делаем улучшение(1): составляем map<string,unsigned> из слов. В качестве слов используем указатели на слова, сравнение указатеелй как чисел (в итоге полностью исключаем сравнение слов, имеем идеальный хеш), но можем потерять на загрузке (составление словаря).

Код:

loaded at 0 secs
sample 72835 words
text 40581 words
took 65 secs
longest match (10): библиотек ладошек http palm com ладошк солнц карманны компьютеры аркад

Уже лучше. Обратите внимание: идеальный хеш ускорил всего (!) в 2 раза.

Другое улучшение(2): Теперь считаем цитаты редкими и составляем map слова на список его вхождений. Убираем хеш, т.е. снова сравниваем строки.

Код:

loaded at 0 secs
sample 72835 words
text 40581 words
took 1 secs
longest match (10): библиотек ладошек http palm com ладошк солнц карманны компьютеры аркад

Более, чем приемлимый результат. Собираем release для улучшений(1) и (2), получаем соотвественно 4 и 0 секунд. Улучшение(2) можно ещё ускорить (по расчётам на порядок), если использовать не map (aka red-black tree), а unordered_map (aka hash table).

Теперь решаем задачу "найти все цитаты". Для этого заметим, что мы их фактически все и находим, находя максимальную. Отличие только в том, как производится выбор лучшего решения из последнего состояния. Вместо вывода на экран самой длинной цепочки, мы выводим все цепочки в порядке убывания длины. Причём после вывода цепочки удаляем её состояния, избегая тем самым пересечения.

Любопытно выглядят цепочки из 3-5 слов. По сути это любимые выражения автора, стиль его разговора. Можно использовать для анализа личности (сравнив несколько писем). Мне понравилась фраза (если правильно помню) "вот уже пять лет как".

т.о. полная задача решена за лучшее время меньше 1 сек. Если считать подписи цитатами подписей, проверять цитирование письмом не только прошлого письма, но и подписи отправителя, то вроде как задача решается.

Внимание, вопрос для разработчиков архиваторов: что будет, если найти все цитаты письма самим себя (по сути все повторения)?.... Правильно! письмо полностью себя цитирует!

Ещё одно возможное применение - diff, который находит не только отличия, но и копипасты.
В принципе задачу можно считать решённой; остаются вопросы с ложными срабатываниями, когда за цитирование будет принят плохой стиль письма.

pva · Отправлено: **13:17, 13-11-2013** | #6

Примеры схожих в двух произведениях фраз:

Код:

longest match (5): разобра можн был тольк отдельны
longest match (5): отдавал себ отч то чт
longest match (5): наскольк эт возможн пр наш
longest match (5): как раз тот момент когд
longest match (4): знаю как эт делаетс
longest match (4): вдруг пришл голов чт
longest match (4): ег покидал ощущени чт
longest match (4): вс вид сво изображ
longest match (4): можн был предположи чт
longest match (4): вдруг пришл голов чт
longest match (4): чт вс эт врем
longest match (4): однак ясн был чт
longest match (4): эт был сам дел
longest match (4): кра глаз вид чт
longest match (4): можн был подума чт
longest match (4): вс дел то чт
longest match (4): почувствовал чт вот сейчас
longest match (4): знаю тольк чт мн
longest match (4): дл тог чтобы убива
longest match (4): мож бы вс дел
longest match (4): тольк дл тог чтобы
longest match (4): вс эт врем он
longest match (4): некотор врем сид неподвижн
longest match (4): человек мож бы даж
longest match (4): знае чт эт так
longest match (4): ем был вс равн
longest match (4): сраз понял чт эт
longest match (4): совершенн невозможн был представи
longest match (4): невозможн был представи себ
longest match (4): сраз понял чт эт
longest match (4): сраз понял чт эт
longest match (4): был совершенн ясн чт
longest match (4): откинулс спинк кресл вот
longest match (4): был совершенн ясн чт
longest match (4): можн был спокойн совестью
longest match (4): уж прост пот чт
longest match (4): взял папк под мышк
longest match (4): простит как вас зовут

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