2 つの文字列を比較する効率的な方法 (文字の順序は関係ありません)

https://stackoverflow.com/questions/1617106

06-07-2019
|

質問

2 つの文字列を比較するアルゴリズムを考え出そうとしています。同じ文字を含む単語の一致を登録します。たとえば、rent と tern はどちらも r、e、n、t という文字を含むため、同等になります。

編集非常に曖昧で申し訳ありません。比較は、数千語の 2 つのセットに対して何百回も行われることになります。これはコード全体のほんの一部にすぎないため、すべてが滞ってしまうことは望ましくありません。

「はい」と尋ねた人にとって、オーバーマッチングは非常に重要です。たとえば、家賃もテルニテニテと一致します。

編集2 rent == ternicate のような一致の場合、ternicate はrentと一致しません。それは、単語 2 に単語 1 の文字が含まれているかのようなものです。したがって、余分な文字がある場合でも、単語に最初の単語のすべての文字が含まれている限り、一致します。

解決

さて、これは本当に悪い考えですが、それは非常にクレイジーなので、動作するかもしれません！

最初の26個の素数のリストを作成します。
```
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, ...]
```
単語の各文字について、対応する素数を見つけます。 <！>＃8594; 2、B <！>＃8594; 3、C <！>＃8594; 5など。
これらの素数を乗算します。最終的に（非常に大きな）番号になります。

同じ文字を持つ単語は同じ番号になります。文字が異なる単語には、異なる番号が付いていることが保証されています。なぜですか？

素数を乗算するため、文字の一意の組み合わせに対して常に一意の製品が生成されます。数字は元の要因に分解され、元の単語にどの文字が含まれているかが正確にわかります。文字の順序は保持されませんが、単語に含まれる文字とその文字数があります。

たとえば、<！> quot; face <！> quot;および<！> quot; cafe <！> quot;。

FACE = 13 * 2 * 5 * 11 = 1430  
CAFE = 5 * 2 * 13 * 11 = 1430

はい！単純な整数比較よりも効率的なものは何ですか？

...

はい、いいえ、そうでないかもしれません。これは、実際に使用するにはあまりにもばかげています。でもすっきりしています。

他のヒント

最初に各文字列の文字を並べ替えてから、比較します。

rent == tern
enrt == enrt

質問のあいまいさを考えると、ここで重要なのは、文字が出現する回数を数えるのにないように見えることです。

したがって、すべての文字がa-zの範囲にあると仮定し、整数インデックスを使用して配列として元の単語リストにインデックスを付けることができると仮定します：

1. 2つの配列（リストごとに1つ）を作成します。

2.両方のリストのすべての単語について、ビットマップを次のように計算します。

bitmap = 0
foreach (character in word) {
    bitmap |= (1 << (character - 'a'))
}
arrayX[index] = bitmap;

このビットマップは、その単語に現れるすべての文字のセットを表します。

3.その後、セットAの各単語について、セットBを反復処理し、次の場合に一致します

arrayA[indexA] | arrayB[indexB] == arrayB[indexB]

このテストは、その単語Aの文字セットが単語Bの文字のサブセットである場合にのみ真になります。<！> quot;または<！> quot;ビットセットの操作は、実際のセットのユニオン（<！>＃8746;）演算子に相当します。

set mathemtatics のWikipediaエントリを参照してください-A <！>＃ 8838; A <！>＃8746;の場合のみB B = B。

ところで、ステップ3はO（n ^ 2）ですが、ビット単位の比較であるため、非常に高速である必要があります。各リストの数千語（〜400万テスト）にかかる時間は1秒未満です。

別の方法の 1 つは、各文字列内の各文字の数を数えて、その数を比較することです。単純な実装には次の時間がかかります O(max(N, A)) ここで、N は文字列の大きい方の長さ、A はカウントを格納するために使用する配列のサイズです。たとえば、Java では次のようになります。

public boolean equalIgnoringOrder(String s1, String s2) {
    if (s1.length() != s2.length()) {
        return false;
    }
    // Assuming characters in the range ASCII 0 to 127 
    int[] c1 = new int[128];
    int[] c2 = new int[128];
    for (int i = 0; i < s1.length(); i++) {
        c1[s1.charAt(i)]++;
        c2[s2.charAt(i)]++;
    }
    for (int i = 0; i < c1.length; i++) {
        if (c1[i] != c2[i]) {
            return false;
        }
    }
    return true;
}

これにはいくつかの改善策が考えられます。たとえば、範囲を縮小することで任意の文字セットに対処できます。つまり最初のパススルーを実行する s1 そして s2 それぞれの文字の最小文字と最大文字を探し、これを使用して文字のサイズを決定します。 c1 そして c2 そしてベースオフセット。これにより、平均して使用するスペースが減り、count 配列の初期化にかかる時間が短縮されます。また、比較のための短絡回路も提供します。例えば最小文字と最大文字の場合 s1 そして s2 同じではありません。

比較すると、ヒープソートまたはクイックソートを使用してソートされた文字列を比較すると、次のようになります。 O(NlogN) 平均して O(N) スペース。N は長い方の文字列の長さです。

ただし、@pst が指摘しているように、比例定数により、 O(NlogN) あるいは O(N*N) よりも優れたアルゴリズム O(N) N が大きくない場合のアルゴリズム。この場合、比較される文字列の平均長がおそらく最も重要な要素となります。

上記のコードは、いくつかの短絡を伴う基数ソートを効果的に実行しています。(範囲縮小に伴う短絡を含めると 3 つです。) したがって、最終的には、クイックソート/ヒープソートと基数ソートのどちらが優れているかということになります。そして、それは入力文字列の長さと文字範囲によって異なります。

別のタックルで。@Johnの答えは、素数の積を計算することを提案しています。任意精度表現を使用して計算を実行すると、結果の値は「順序を無視した等しい」文字列の個別のセットごとに一意になります。残念ながら、計算は次のようになります。 O(N*N). 。（各中間生成物には O(N) N 桁の数値に定数を掛けると、 O(N). 。これを N 文字分実行すると、次のようになります。 O(N*N).)

しかし、(たとえば) 64 を法とする計算を実行すると、結果は事実上、文字順序に影響されない非常に優れたハッシュになります。例えば

long hash = 1;
for (int i = 0; i < s.length(); i++) {
    hash = hash * primes[s.charAt(i)];
}

したがって、最高のパフォーマンスとスペース使用量を実現するアルゴリズムは次のとおりであると私は主張します。 平均して ランダムに生成された文字列を比較する場合、次の形式になる可能性があります。

if (s1.length() != s2.length()) {
    return false;
}
if (hash(s1) != hash(s2)) { // computed as above
    return false;
}
// Compare using sorting or character counting as above.

最後にもう 1 点。文字列ポインタが同一ではなく、文字列の長さが異なると仮定すると、これを計算するアルゴリズムは equals 述語 である必要があります で O(N) あるいはさらに悪いことに。この決定を行うには、両方の文字列内のすべての文字を検査する必要があり、それには時間がかかります O(N) オペレーション。

以下のことを行うアルゴリズム 2 * N フェッチ以下 2 * N フェッチされた値に対するさらなる操作 このシナリオでは は明らかに間違っています。

Stephen Cに同意する必要があります-これは答えるほど十分に定義されていません。

降格するつもりはありませんが、たとえば、家賃がterrentと同等であるかどうかを説明してもらえますか？あなたは、それがそうであると仮定している回答者を持っています（発生の数は重要ではないと考えている人々と、最悪の事態を仮定する他の回答者。これらのグループの1つは彼らの時間を浪費しています。

また、あなたの懸念はパフォーマンスに関するものなので、私たちはあなたの呼び出しパターンについてもっと知る必要があります。セットのペアを複数回見るかどうか、またはセットが異なるかどうかを説明できますか？

用語の単調さとして、あなたはすでにこれを知っているかもしれませんが、現在の定式ではアルゴリズムは対称的ではありません。

家賃はテルニケートと一致すると言いますが、明らかに、テルニケートは家賃と一致しません。 つまり、等価性を本当に探しているわけではありません。 <！> quot;が<！> quot;または<！> quot; from made from <！ > quot;。

これは、順序に注意する必要があることを意味します。セットにアクセスする方法に応じて、異なる結果が得られます。

誤解しないでください：興味深い問題です...問題が何なのかわかりません。

高速ではないかもしれませんが、java + google-collections + guavaを使用した最短のソリューション（char[]-<！> gt; List<Character>のキャスト用）

import com.google.common.collect.ImmutableMultiset;
import com.google.common.primitives.Chars;

public class EqualsOrderignore {
private static boolean compareIgnoreOrder(final String s1, String s2) {
    return ImmutableMultiset.copyOf(Chars.asList(s1.toCharArray()))
            .equals(ImmutableMultiset.copyOf(Chars.asList(s2.toCharArray())));
} 
}

このアルゴリズムの実行時：O（s1.length + s2.length）

iは、このソリューションが-server VM上で手作りのO（N1 + N2）ソリューションと同等の性能を発揮することを確信しています。

プラスとして、このソリューションは、a-Zだけでなく、あらゆる文字のインスタンスに対して機能します。

ワードゲームやアナグラムで動作する多くのコードを作成しました。通常のアプローチは、単語をソート済みキーに変換し、前述のように、「rent」が「tern」に一致するようにすることです。これは、両方が「enrt」にマップされるためです。ただし、このルートを開始すると、文字と出現回数の辞書があれば非常に役立ちます。以下は、ソートされていない文字列を（key = character、value = count）で辞書に変換するpythonコードです：

import collections

# Create a defaultdict(int) from a string
def create_collections_dict(key):
    dk = collections.defaultdict(int)
    for k in key:
        dk[k] += 1
    return dk

共通の文字数を即座に確認することで、他の人に対して単語をスコアリングできます：

# Score the similarity of a defaultdict(int) against a string
# (which is temporarily converted to a defaultdict(int))
def score(dk, cand) :
    dc = create_collections_dict(cand)
    return sum(min(dk[k], dc[k]) for k in dk.keys() if k in dc)

if __name__ == '__main__':
    base = create_collections_dict('rent')
    for word in ['tern', 'ternicate', 'foobar']:
        print word, score(base, word)

結果：

tern 4
ternicate 4
foobar 1

仮定：

あなたの言葉はアスキー文字のみで構成されています
大文字小文字は関係ありません
abcはabcdeと一致し、abcdeはabcと一致しません

文字をカウントして一致文字列（s2）を通過し、値（s1）を通過して、他にすべての文字が存在することを確認できます（疑似コード、未確認）：

boolean matches(String s1, String s2) {
   int[]  counts = new int[256];
   char[] c1;
   char[] c2;

   c1 = s1.getCharArray();
   c2 = c2.getCharArray();

   // count char occurences in longest string
   for (int n = 0; n < c2.length; n++) {
       counts[(int)c2[n]]++;
   }

   // check all chars in shortest string are foud in the longest
   for (int n = 0; n < c1.length; n++) {
       if (0 == counts[(int)c1[n]]) {
          return false;
       }
   }

   return true;
}

これは、引数の長さの合計に対してO（n）になります。

編集：質問はs1とs2の間の非対称関数に変更されました。

かなりあいまいですが、連想配列を使用して解決します：

各単語の各文字を、整数の連想配列のキーとして使用します。 1つの単語の文字は値を増やし、もう1つの文字は値を減らします。最後に、すべてのキーに対してforeachを実行し、すべての値がゼロであることを確認してから、一致します。これにより、基本的なrent == tren機能が得られます。

あいまいさに関する警告： 1.複数の文字が問題ない場合、たとえばrent == rreennttの場合、配列に文字を追加するときは、キーが存在するかどうかを確認し、存在する場合は再度追加しないでください。
2.余分な文字、たとえばrent == renterであるがfernt！= renterである場合、最後に配列の値を確認するとき、1と-1が同時に配列にないことを確認します。言い換えると、1と0のみが大丈夫、または-1と0が大丈夫ですが、1と-1が同時に配列に入れることはできません。

これが他のアプローチに比べてどれくらい速いかはわかりませんが、実装は簡単です。

ツリーを構築する必要があると思います。アイデアを説明するためにPythonコードを少し書きましたが、おそらくバグがあります：

class knot():
    def __init__(self, char, is_word, string = "" way = 0):
        self.children = []
        self.shortest_way = way
        self.char = char
        self.word = is_word
        self.string = string

def comparing(strings):
    sorted_strings = []
    for string in strings:
        array_of_string = []
        for char in string:
            array_of_string.append(char)
        sorted_strings.append(array_of_string.sort())
    sorted_strings.sort()

    start = []
    matches = []

    for array_of_string in sorted_strings:
        matches += insert_string(array_of_string, start)

def insert_string(array, start):
    for match_string in test_string(array, start):
        matches += (array, match_string.string)
    add_string(array, start, 0):

def add_string(array, knots, n):
    minimum = 0
    maximum = len(knots) - 1
    while minimum != maximum:
        num = int((minimum + maximum) / 2)
        if (knots[num].char > array[n]):
            minimum = num
        elif (knots[num].char < array[n]):
            maximum = num
        elif (knots[num].char == array[n]):
            return add_string(array, knots[num], n+1)
    knots.append(new_knots(array, n))
    knots.sort

    """ more insertion routine needed"""

def search_children(array, knots):
    minimum = 0
    maximum = len(knots) - 1
    while minimum != maximum:
        num = int((minimum + maximum) / 2)
        if (knots[num].char > array[0]):
            minimum = num
        elif (knots[num].char < array[0]):
            maximum = num
        elif (knots[num].char == array[0]):
            return test_string(array, knots[num])
    return []

def test_string(array, target_knot):
    if len(array) > target_knot.sortest_way + 1:
        return []
    match_knots = []
    if len(array) == 1 and target_knot.is_word == True:
        match_knots.append(target_knot)
    for i in range(1, len(array)):
        match_knots += search_children(array[i:], target_knot.children)
    return match_knots

サブセットを探しているだけで、一般的な英語の文字に限定されていると仮定すると、効率的なヒストグラムで十分です。 64ビットの符号なし整数を使用して、最大2つのオカレンスをカウントするための2ビットと、オーバーフローフラグを追加し、「e t a o i n s r h l d」の最大3つのオカレンスをカウントするための追加の12ビットを使用します。バイナリを使用するのではなくビットが埋められます（したがって、3つの 'e'の場合、111になります。サブセットの関係をテストするには、テストするサブセットのオーバーフロービットをチェックし、設定されていない場合は、ビット単位で使用してサブセットをテストできます。ヒストグラムがオーバーフローした場合、文字列のソートされた内容のO（Length）チェックにフォールバックします。

選択したアルゴリズムにかかわらず、同じ長さの文字列に対して最適化が行われる場合があります。あなたがしなければならないのは、各文字のXORです。結果が0の場合、それらは同じ文字を含みます。これは部分文字列の場合には役立ちませんが、より高価な比較を短絡する助けになるかもしれません。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow