Алгоритм сравнения нескольких текстов

Question

Учитывая несколько текстов, которые немного отличаются друг от друга (некоторые слова отсутствуют/заменены другими словами), есть ли хороший алгоритм для создания своего рода «шаблона»? Например:

Input: 
- Hello my name is Bob 
- Hi my name is Bob 
- Hi my name is John 

Output: 
- * my name is * 

Алгоритм должен быть максимально толерантными, как можно отклоняющихся значений, например, если добавить четвертый вход:

- Hello i am Bob 

Это не должно влиять на результат слишком много.

Answer 1

Существует аналогичная проблема в биологии: http://en.wikipedia.org/wiki/Consensus_sequence

Answer 2

Это, как я бы реализовать. Это не фантазия или использование лучшего подхода, но делает трюк!

Я использовал java для реализации, и вы можете извлечь из него алгоритм.

public static String matchText(List<String> textsSet) 
{ 
    double maxWeight = 0; 
    String subStringMaxWeight = ""; 

    // create a table to store all substring occurrences 
    Hashtable<String, Integer> subStringsSet = new Hashtable<String, Integer>(); 

    // starts a loop through text's list 
    for (String text : textsSet) 
    { 
     // splits text into words (separeted by spaces) 
     String[] subStrings = text.split(" "); 
     // if text has more than 1 word, then we are considering it as a "phrase" 
     if (subStrings.length > 1) 
     { 
      // starts a loop to generate all possible word combination 
      // "aaa bbb ccc ddd eee" text will generate these combinations: 
      // aaa bbb 
      // aaa bbb ccc 
      // aaa bbb ccc ddd 
      // aaa bbb ccc ddd eee 
      //  bbb ccc 
      //  bbb ccc ddd 
      //  bbb ccc ddd eee 
      //   ccc ddd 
      //   ccc ddd eee 
      //    ddd eee 
      for (int posIni = 0; posIni < subStrings.length-1; posIni++) 
      { 
       for (int posEnd = posIni + 1; posEnd < subStrings.length; posEnd++) 
       { 
        StringBuilder subString = new StringBuilder(); 

        // if posIni is not the first word, adds * at the begining 
        if (posIni > 0) 
         subString.append("*"); 

        // generate the substring from posIni to posEnd 
        for (int pos = posIni; pos <= posEnd; pos++) 
        { 
         if (subString.length() > 0) 
          subString.append(" "); 
         subString.append(subStrings[pos]); 
        } 

        // if posEnd is not the last word, adds * at the end 
        if (posEnd < subStrings.length - 1) 
         subString.append(" *"); 

        // check if substring already exists in the Hashtable      
        Integer counter = subStringsSet.get(subString.toString()); 
        if (counter == null) 
        { 
         // substring does not exist, so stores it with the counter = 1 
         counter = new Integer(1); 
         subStringsSet.put(subString.toString(), counter); 
        } 
        else 
        { 
         // substring exists, so increments it's counter 
         subStringsSet.remove(subString.toString()); 
         counter = new Integer(counter.intValue() + 1); 
         subStringsSet.put(subString.toString(), counter); 
        } 

        // calculate the weight of the substring based on the number of occurrences plus weight based on the number of words. 
        // counter has heavier weight, but the number of words also has some weight (defined here as 0.05 - feel free to change it) 
        double weight = counter.intValue() + ((posEnd - posIni + 1) * 0.05); 
        if (weight > maxWeight) 
        { 
         maxWeight = weight; 
         subStringMaxWeight = subString.toString(); 
        } 

       } 

      } 
     } 
    } 
    // returns the substring 
    return subStringMaxWeight;