交換可能な文字列を保持するためのデータ構造

Question

私は一連の文字列を持っています。これらのうち、2つ以上のグループが同じものを表すことがあります。これらのグループは、グループのメンバーがあれば、グループの他のメンバーを効率よく取り出すことができるように格納する必要があります。

だから、この初期セットを与えられた： ["a","b1","b2","c1","c2","c3"]結果構造が ["a",["b1","b2"],["c1","c2","c3"]]のようなものになると ["b1","b2"]を返す必要があります（「B」）を取得する必要があります。

この目的のための特定のデータ構造および/またはアルゴリズムはありますか？

EDIT： "b1"と "b2"は実際の文字列ではなく、2つが同じグループに属することを示しています。それ以外の場合、Trieは完璧にフィットします。

Answer 1

私は最初の問題設定を誤解しているかもしれませんが、私は既成のデータ構造を使ってこの問題を解決する簡単で洗練されたソリューションがあると信じています。アイデアは、高レベルで、文字列から文字列のセットへのマップを作成することです。マップの各キーは、それと等しい文字列のセットに関連付けられます。グループ内の各文字列が同じ文字列にマップされていると仮定すると、これは時間と空間を効率的に行うことができます。

アルゴリズムは、おそらく次のようになります。

1. 文字列のセットに、文字列からマップMを構築します。
2. すべての文字列を互いに等しくグループ化します（この手順は、文字列とグループの指定方法によって異なります）。
3. 各クラスタについて：
   1. そのクラスタに標準的な文字列を作成します。
   2. 各文字列を、値が正規のセットであるキーとしてマップに追加します。

このアルゴリズムは、得られたデータの構造は非常に効率的です。事前にクラスターを知っていると仮定すると、マップの実装としてのトライとセットのデータ構造としての単純なリストを使用するこのプロセスでは、各入力文字列の各文字を正確に2回、それをトライに入れ、一度それをそれに等しい文字列のセットに追加すると、深いコピーを作っていると仮定します。したがって、これはO（n）アルゴリズムです。

さらに、ルックアップは非常に高速です。文字列のセットをいくつかの文字列に一致させるには、トライを歩いて文字列を検索し、関連付けられた文字列を検索してから繰り返します。これはO（L + k）時間を要し、ここでLは文字列の長さであり、kはマッチの数である。

私が問題文を誤解している場合は、これが役立ちます。

Answer 2

これはJavaであるため、HashMap<String, Set<String>>を使用します。これは、各文字列を同値集合（その文字列と同じグループに属する他のすべての文字列）にマップします。入力から等価集合をどのように構築するかは、 "等価"をどのように定義するかによって決まります。入力が（実際にグループ化されていない）グループによって順になっている場合は、述語が等価性をテストするために実施していた場合、及び、あなたはこのような何かを行うことができ：グループであれば、この唯一の作品が連続していることを

boolean differentGroups(String a, String b) { 
    // equivalence test (must handle a == null) 
} 

Map<String, Set<String>> makeMap(ArrayList<String> input) { 
    Map<String, Set<String>> map = new HashMap<String, Set<String>>(); 
    String representative = null; 
    Set<String> group; 
    for (String next : input) { 
     if (differentGroups(representative, next)) { 
      representative = next; 
      group = new HashSet<String>(); 
     } 
     group.add(next); 
     map.put(next, group); 
    } 
    return map; 
} 

注意を入力内の要素そうでない場合は、グループ構造を構築するためにさらに複雑な簿記が必要になります。