4

「複数の名前配列が与えられた場合、長さ 3 の名前の最も頻繁に発生するシーケンス (長さ 3 のシーケンス) が存在する場合は、それを見つけます」

例: 3 つの名前配列が与えられた場合:

Ana John Maria
Paul
Sharon Ana John Maria Tiffany Ted

Ana John Mariaこのシーケンスは最初と 3 番目の配列で 2 回発生するため、出力は になります。

これに対する正しい解決策が見つからないようです。

誰かが私を正しい方向に向けることができますか? 多分それはこれのためのよく知られたアルゴリズムです。誰でも私にリンクを教えてもらえますか？ありがとう

4

2 に答える 2

4

配列を trie に似たツリーにマージします。各ノードは単一の文字ではなく、名前全体です。これにより、サブシーケンスをより簡単に見つけてカウントできるようになります。実際、このタスクには参照できる標準アルゴリズムがあるのではないかと強く思っています。

更新: サフィックス ツリーを使用したアルゴリズムを参照してください: http://en.wikipedia.org/wiki/Suffix_tree

于 2012-08-15T16:55:08.130 に答える
2

簡単なアプローチは、3のシーケンスを取り、それらを。に入れることHashTableです。3のシーケンスに遭遇するとすぐに、対応するオカレンスカウンターをインクリメントします。最後に、最も頻繁に発生する/シーケンスを返すだけHashTableです。これは、最大発生値を持つエントリをスキャンすることで検出されます。Javaでの例：

public class Sequence {  
     public List<String> sequenceOfThree(List<List<String>> names){
          Map<List<String>, Integer> map = new HashMap<List<String>, Integer>();  
          for(List<String> nameList:names){  
              int startIdx = 0;
              int endIdx = 3;
              while(endIdx <= nameList.size()){  
                   List<String> subsequence = nameList.subList(startIdx, endIdx);  
                   //add to map  
                   Integer count = map.get(subsequence);  
                   if(count == null){  
                         count = 0;  
                   }  
                   map.put(subsequence, count + 1);  
                   startIdx++;  
                   endIdx++;  
              }  
          }  
          Integer max = Integer.MIN_VALUE;  
          List<String> result = Collections.emptyList();  
          for(Entry<List<String>, Integer> entries:map.entrySet()){  
              if(entries.getValue() > max){  
                  max = entries.getValue();  
                  result = entries.getKey();  
          }
      }  
      return result;  
  }  
  /**  
   * @param args  
  */  
   public static void main(String[] args) {  
         List<List<String>> names = new ArrayList<List<String>>();  
         names.add(Arrays.asList(new String[]{"Ana", "John", "Maria"}));  
         names.add(Arrays.asList(new String[]{"Paul"}));  
         names.add(Arrays.asList(new String[]  
{"Sharon", "Ana", "John", "Maria", "Tiffany" ,"Ted"}));  
        System.out.println(new Sequence().sequenceOfThree(names));  
   }  
}
于 2012-08-15T18:17:51.863 に答える