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