同じ文字を使用して、最も近い文字列を検索するためのアルゴリズム

StackOverflow https://stackoverflow.com/questions/859441

  •  21-08-2019
  •  | 
  •  

質問

n個の文字列のリストL、および入力された文字列Sを考えると、Sに存在するほとんどの文字が含まれているLの文字列を検索するための効率的な方法は何ですか？私たちは、最も密接Sに含まれる文字で構成されてL内の文字列を検索する。

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

単純なループよりも良い方法はありますか？データ構造は、私は私の高速検索機能を与えることに、n個の文字列を読み込むことができますがありますか？ループよりも優れて実行することになり、n個の文字列のそれぞれについて、事前に計算されたメタデータを使用するアルゴリズムはありますか？

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

ありがとうございます。

役に立ちましたか？

解決

あなたが部分文字列の後にある場合は、

、トライするまたはPatricaトライは良い出発点かもしれませんます。

あなただけの各記号や文字の数については、順序を気にしない場合は、

、私はすべての文字列のヒストグラムを計算し、入力のヒストグラムとそれらを比較します。

               ABCDEFGHIJKLMNOPQRSTUVWXYZ
Hello World => ...11..1...3..2..1....1...
あなたが唯一の大文字と小文字を区別しないラテン文字を考慮すれば、

このは一度O(26 * m + n)するコストプラスの前処理が低下します。

mが一定であれば、あなたはそれを正規化することにより、26次元単位球上の26次元ベクトルとしてヒストグラムを解釈することができます。次に、あなただけの2つのベクトルのhref="http://en.wikipedia.org/wiki/Dot_product" rel="nofollow noreferrer">内積には、2つの間の角度の余弦を得

m = 3、サイズのみ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)のrユークリッドノルムでhために正規化される - 。r = 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)を有している。

次に、我々は両方のヒストグラムのユークリッド距離ように、2つのヒストグラムのh1 = (a, b, c)と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ノルム） - - 一つは、他の基準を使用することができるが、有限次元ベクトル空間内の規範は、すべて等価であるので、これは数字のみを変更します

。

他のヒント

あなたはトライに必要なように、

が鳴ります。試行は、スペルチェッカーが動作する方法に類似した単語を検索するために使用されています。文字列Sは、Lの文字列と同じ順序で文字が含まれているのであれば、これはあなたのために働くことがあります。

ただし、Sの文字の順番は関係ありません - スクラブルのタイルのセットのように、あなたが最も長い単語を検索したい - これはあなたのソリューションではありません。

何が欲しいのは BK-ですツリーに。それは少しわかりにくいが、非常にクールだ - 。それは（log n）時間のレーベンシュタイン（編集）Oにおける距離閾値内の要素を検索することが可能となる。

あるとして

あなたが入力文字列に注文を気にしている場合、それらを使用しています。そうしない場合は、BK-ツリーに挿入する（またはそれらを照会する）前に、個々の文字を並べ替えることができます。

私はここで見つけることができるか、あなたが探していると信じて：<のhref = "http://publications.drdo.gov.in/gsdl/collect/dbit/index/assoc/HASH5495.dir/dbit2406003.pdf "REL =" nofollowをnoreferrer ">ファジー論理ベースの検索技術の

これはかなり重いですが、そうあなたが求めているものです。これは、単語の類似性、および文字位置ずれについて語っています。

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

文字の順序があなたの問題では重要ではありませんが、あなたが単語Sの「ニアアナグラム」を探しているように私には思える。

それがそうなら、

、あなたは26の整数（あなたのアルファベットは26個の文字を持っていると仮定）の配列としてセットL内のすべての単語を表すことができます。あなたは26個の整数の配列と同様にSを表すことができます。今、あなただけのセットLを一度実行し、S-ベクトルと現在のL-ベクトル間の距離メトリックを計算するベストマッチを見つけるには、しかし、あなたは距離メトリック（例えばユークリッド/の二乗和やマンハッタンを定義したいです絶対差の/合計）。ベクターは、一定の長さを有しているので、これはO（n）のアルゴリズムである。

ここでは、私にとって素晴らしい仕事をしている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
ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top