4

n 個の文字列のリスト L と入力文字列 S が与えられたとき、S に存在する最も多くの文字を含む L 内の文字列を見つける効率的な方法は何ですか? S に含まれる文字で最も密接に構成されている L の文字列を見つけたいとします。

明白な答えは、すべての n 文字列をループして、現在の文字列の文字数が S に存在するかどうかを確認することです。ただし、このアルゴリズムは頻繁に実行され、n 文字列のリスト L がデータベースに格納されます... n 個の文字列すべてを手動でループするには、n*m^2 の big-Oh のようなものが必要になります。ここで、n は L 内の文字列の数、m は L 内の任意の文字列の最大長、および S の最大長です。 ... この場合、m は実際には 150 の定数です。

単純なループよりも良い方法はありますか? n 個の文字列を読み込むことができるデータ構造はありますか?高速検索機能を提供しますか? ループよりも優れたパフォーマンスを発揮する n 個の文字列のそれぞれについて、事前に計算されたメタデータを使用するアルゴリズムはありますか?

アルゴリズムに夢中になっているオタクがたくさんいることは知っています。だから助けてください！

ありがとう！

4

6 に答える 6

6

部分文字列が必要な場合は、トライまたはパトリカトライが出発点として適している可能性があります。

順序を気にせず、各記号または文字の数だけを気にする場合は、すべての文字列のヒストグラムを計算し、それらを入力のヒストグラムと比較します。

               ABCDEFGHIJKLMNOPQRSTUVWXYZ
Hello World => ...11..1...3..2..1....1...

O(26 * m + n)大文字と小文字を区別しないラテン文字のみを考慮する場合、これによりコストが削減され、前処理が 1 回行われます。

m が定数の場合、正規化することにより、ヒストグラムを 26 次元単位球上の 26 次元ベクトルとして解釈できます。次に、2 つのベクトル間の角度のコサインを生成する 2 つのベクトルの内積を計算するだけで、この値は文字列の類似度に比例するはずです。

、サイズ 3 のみm = 3のアルファベット、および次の文字列のリストを想定します。A = { 'U', 'V', 'W' }

L = { "UUU", "UVW", "WUU" }

ヒストグラムは次のとおりです。

H = { (3, 0, 0), (1, 1, 1), (2, 0, 1) }

ヒストグラムは、ヒストグラムのユークリッド ノルム、つまり に正規h = (x, y, z)化されh' = (x/r, y/r, z/r)ます。rhr = sqrt(x² + y² + z²)

H' = { (1.000, 0.000, 0.000), (0.577, 0.577, 0.577), (0.894, 0.000, 0.447) }

入力S = "VVW"には、ヒストグラムhs = (0, 2, 1)と正規化されたヒストグラムがありhs' = (0.000, 0.894, 0.447)ます。

h1 = (a, b, c)これで、2 つのヒストグラムの類似性をh2 = (x, y, z)、両方のヒストグラムのユークリッド距離として計算できます。

d(h1, h2) = sqrt((a - x)² + (b - y)² + (c - z)²)

取得した例について。

d((3, 0, 0), (0, 2, 1)) = 3.742
d((1, 1, 1), (0, 2, 1)) = 1.414
d((2, 0, 1), (0, 2, 1)) = 2.828

したがって、「UVW」は「VVW」に最も近いです (数字が小さいほど類似性が高いことを示します)。

正規化されたヒストグラムを使用するh1' = (a', b', c')とh2' = (x', y', z')、両方のヒストグラムの内積として距離を計算できます。

d'(h1', h2') = a'x' + b'y' + c'z'

取得した例について。

d'((1.000, 0.000, 0.000), (0.000, 0.894, 0.447)) = 0.000
d'((0.577, 0.577, 0.577), (0.000, 0.894, 0.447)) = 0.774
d'((0.894, 0.000, 0.447), (0.000, 0.894, 0.447)) = 0.200

ここでも、「UVW」が「VVW」に最も近いと判断されます (数値が大きいほど類似性が高いことを示します)。

どちらのバージョンでも数値は異なりますが、結果は常に同じです。たとえば、マンハッタン距離 (L1 ノルム) など、他のノルムを使用することもできますが、有限次元ベクトル空間のノルムはすべて同等であるため、これは数値のみを変更します。

于 2009-05-13T18:20:13.813 に答える
1

あなたが欲しいのはBK-Treeです。少し直感的ではありませんが、非常にクールです。また、O(log n) 時間でレーベンシュタイン (編集) 距離しきい値内の要素を検索できます。

入力文字列の順序が気になる場合は、そのまま使用してください。そうでない場合は、個々の文字を BK ツリーに挿入する (またはクエリを実行する) 前に並べ替えることができます。

于 2009-05-13T23:18:13.157 に答える
1

トライが必要なようですね。試行は、スペル チェッカーが機能するのと同様の方法で単語を検索するために使用されます。したがって、String S に L の Strings と同じ順序で文字が含まれている場合、これでうまくいく可能性があります。

ただし、S の文字の順序が関係ない場合 (スクラブル タイルのセットのように、最も長い単語を検索したい場合)、これは解決策ではありません。

于 2009-05-13T18:08:20.993 に答える
0

あなたが探しているものはここで見つかると思います:ファジーロジックベースの検索テクニック

それはかなり重いですが、それはあなたが求めているものです。単語の類似性と文字の配置ミスについて説明します。

i.e:

L I N E A R T R N A S F O R M
L I N A E R T R A N S F O R M
L E N E A R T R A N S F R M
于 2009-05-13T19:02:04.807 に答える
0

これは、私にとってうまく機能しているT-SQL関数で、編集距離を示します。

例：

  SELECT TOP 1 [StringValue] , edit_distance([StringValue, 'Input Value')
    FROM [SomeTable]
ORDER BY edit_distance([StringValue, 'Input Value')

関数：

CREATE FUNCTION edit_distance(@s1 nvarchar(3999), @s2 nvarchar(3999))
RETURNS int
AS
BEGIN
  DECLARE @s1_len int, @s2_len int, @i int, @j int, @s1_char nchar, @c int, @c_temp int,
    @cv0 varbinary(8000), @cv1 varbinary(8000)
  SELECT @s1_len = LEN(@s1), @s2_len = LEN(@s2), @cv1 = 0x0000, @j = 1, @i = 1, @c = 0
  WHILE @j <= @s2_len
    SELECT @cv1 = @cv1 + CAST(@j AS binary(2)), @j = @j + 1
  WHILE @i <= @s1_len
  BEGIN
    SELECT @s1_char = SUBSTRING(@s1, @i, 1), @c = @i, @cv0 = CAST(@i AS binary(2)), @j = 1
    WHILE @j <= @s2_len
    BEGIN
      SET @c = @c + 1
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j-1, 2) AS int) +
        CASE WHEN @s1_char = SUBSTRING(@s2, @j, 1) THEN 0 ELSE 1 END
      IF @c > @c_temp SET @c = @c_temp
      SET @c_temp = CAST(SUBSTRING(@cv1, @j+@j+1, 2) AS int)+1
      IF @c > @c_temp SET @c = @c_temp
      SELECT @cv0 = @cv0 + CAST(@c AS binary(2)), @j = @j + 1
    END
    SELECT @cv1 = @cv0, @i = @i + 1
  END
  RETURN @c
END
于 2010-09-27T06:05:38.657 に答える
0

問題では文字の順序は重要ではないように思えますが、Sという単語の「アナグラムに近い」を検索しています。

その場合、セット L 内のすべての単語を 26 個の整数の配列として表すことができます (アルファベットが 26 文字であると仮定します)。同様に、S を 26 個の整数の配列として表すことができます。最適な一致を見つけるには、セット L を 1 回実行し、S ベクトルと現在の L ベクトルの間の距離メトリックを計算しますが、距離メトリックを定義する必要があります (例: ユークリッド / 平方和またはマンハッタン) /絶対差の合計）。ベクトルの長さが一定であるため、これは O(n) アルゴリズムです。

于 2009-05-13T20:42:43.143 に答える