Какие методы / инструменты существуют для обнаружения общих фраз в кусках текста?

Question

Допустим, у меня есть 100000 тел электронной почты, и в 2000 из них есть обычная обычная строка типа «быстрая коричневая лиса перепрыгивает через ленивую собаку» или «lorem ipsum dolor sit amet». Какие приемы можно / нужно использовать, чтобы «добыть» эти фразы? Я не заинтересован в поиске отдельных слов или коротких фраз. Также мне нужно отфильтровать фразы, которые я уже знаю, встречаются во всех письмах.

Пример:

string mailbody1 = "Welcome to the world of tomorrow! This is the first mail body. Lorem ipsum dolor sit AMET. Have a nice day dude. Cya!";
string mailbody2 = "Welcome to the world of yesterday! Lorem ipsum dolor sit amet Please note this is the body of the second mail. Have a nice day.";
string mailbody3 = "A completely different body.";
string[] mailbodies = new[] {mailbody1, mailbody2, mailbody3};
string[] ignoredPhrases = new[] {"Welcome to the world of"};

string[] results = DiscoverPhrases(mailbodies, ignoredPhrases);

В этом примере я хочу, чтобы функция DiscoverPhrases возвращала "lorem ipsum dolor sit amet" и "хорошего дня". Это не так важно, если функция также возвращает более короткие «шумовые» фразы, но если это возможно, было бы неплохо устранить их в процессе.

Редактировать: я забыл включить mailbody3 в пример.

Answer 1

Посмотрите на N -грамм . Наиболее распространенные фразы обязательно будут содержать наиболее распространенные N -граммы. Я бы начал с триграмм слов и посмотрел, к чему это приведет. (Требуемое пространство в N раз превышает длину текста, поэтому вы не можете позволить N стать слишком большими.) Если вы сохраняете позиции, а не только счет, вы можете затем посмотрите, можно ли расширить триграммы, чтобы образовать общие фразы.

Answer 2

Нечто подобное может работать, в зависимости от того, заботитесь ли вы о границах слов. В псевдокоде (где LCS - это функция для вычисления Longest Common Subsequence ):

someMinimumLengthParameter = 20;
foundPhrases = [];

do {
    lcs = LCS(mailbodies);
    if (lcs in ignoredPhrases) continue;

    foundPhrases += lcs;

    for body in mailbodies {
        body.remove(lcs);
    }    
} while(lcs.length > someMinimumLengthParameter);

Answer 3

Я не уверен, что это то, что вам нужно, но посмотрите самая длинная общая проблема с подстрокой и алгоритмы утилит diff.