7

q-gramを使用してファジーマッチングを実行したい300万人のレコードを含むテーブルがあります（姓など）。これにリンクする 2 グラムのテーブルを作成しましたが、このデータ ボリューム (約 5 分) では検索パフォーマンスが高くありません。

基本的に 2 つの質問があります: (1) テーブル スキャンを回避するためにパフォーマンスを改善する方法を提案できますか (つまり、検索文字列と 300 万の姓の間で一般的な q-gram をカウントする必要があります) (2) q-gram を使用する場合、Aは B に似ており、C は B に似ていますが、それは C が A に似ていることを意味しますか?

敬具

ピーター

4

4 に答える 4

10

確かにあいまいなテキスト検索をどこでも見たことがあるでしょう。たとえば、「stck」と入力すると、実際には「スタック」を意味します! これがどのように機能するのか疑問に思ったことはありませんか？

ファジー テキスト マッチングを行うアルゴリズムはたくさんありますが、それぞれに長所と短所があります。最も有名なものは、編集距離と qgram です。今日は qgram に焦点を当て、サンプルを実装したいと思います。

基本的に、qgram はリレーショナル データベースに最も適したファジー文字列マッチング アルゴリズムです。とてもシンプルです。qgram の「q」は、2-gram や 3-gram、さらには 4-gram などの数字に置き換えられます。

2 グラムとは、すべての単語が 2 つの文字グラムのセットに分割されることを意味します。"Stack" は {"st", "ta", "ac", "ck"} のセットに分割されるか、"database" は {"da","at","ta","ab に分割されます"、"ba"、"as"、"se"}.

単語が 2 グラムに分割されると、1 つの文字列ではなく一連の値をデータベースで検索できます。たとえば、ユーザーが「stck」と入力を間違えた場合、「a」が欠落しているため、「stck」の検索は「stack」と一致しませんが、2 グラム セット {"st","tc","ck"} には 2 つの行があります。スタックの2グラムセットと共通！ビンゴはかなり近い試合を見つけました。データベースの 2 グラム セットと共通点はなく、「stat」の 2 グラム セットとの共通点は 1 つだけなので、最初に「stack」または 2 番目に「star」と入力するつもりだったことをユーザーに簡単に示唆できます。 "。

それでは、Sql Server を使用して実装してみましょう。仮説的な単語データセットを想定します。2gram と単語の間に多対多の関係が必要です。

CREATE TABLE Grams(twog char(2), wordId int, PRIMARY KEY (twog, wordId))

Grams テーブルは、最初の 2 つの g でクラスター化し、次にパフォーマンスのために wordId でクラスター化する必要があります。単語 (例: スタック) をクエリするときは、グラムを一時テーブルに入れます。まず、数百万のダミー レコードを作成します。

--make millions of 2grams
 DECLARE @i int =0
 WHILE (@i<5000000)
 BEGIN
-- a random 2gram
 declare @rnum1 char = CHAR(CAST(RAND()*28 AS INT)+97)
 declare @rnum2 char = CHAR(CAST(RAND()*28 AS INT)+97)
 INS... INTO Grams (twog, wordId) VALUES ( @rnum1 + @rnum2, CAST(RAND()*100000 AS int))
 END

ここで、「stack」という単語をクエリしてみましょう。これは {'st','ta','ac','ck'} 2 グラムに分割されます。

DECLARE @word TABLE(twog char(2)) -- 'stack'
 INS... INTO @word VALUES ('st'), ('ta'), ('ac'), ('ck')

select wordId, count(*) from @word w inner join Grams g ON w.twog = g.twog
 GROUP BY wordId

このクエリを実行するために、Sql Server が一連のクラスター化されたインデックス シーク (またはルックアップ) を使用していることを確認する必要があります。これは当然の選択ですが、統計が破損していたり​​、古くなっている場合があり、SqlServer がフル スキャンの方が安価であると判断する場合があります。これは通常、左側のテーブルのカーディナリティがわからない場合に発生します。たとえば、SqlServer は @word テーブルが巨大であり、数百万回のルックアップが完全なインデックス スキャンよりもコストがかかると想定する場合があります。

于 2011-09-21T05:54:32.647 に答える
6

私は最近、あいまいな文字列の一致を調べていたので、放棄された質問に答えるリスクがあっても、ここに行きます。これが役に立つことを願っています。

編集距離が特定の値よりも小さい文字列のみに関心があると思います。そして、あなたのqグラム（またはnグラム）は次のようになります

2-grams for "foobar": {"fo","oo","ob","ba","ar"}

  1. 位置qグラムを使用できます：

    "foobar": {("fo",1),("oo",2),("ob",3),("ba",4),("ar",5)}

    位置情報は、一致する q-gram が本当に「良い一致」であるかどうかを判断するために使用できます。

    たとえば、最大編集距離 2 で「foobar」を検索している場合、これは、次の単語のみに関心があることを意味します。

    2-gram "fo" exists in with position from 1 to 3 or
2-gram "oo" exists in with position from 2 to 4 or
... and so on

    文字列「barfoo」は、一致する 2 グラムの位置が 3 異なるため、一致しません。

  2. また、編集距離と一致する q-gram の数との関係を使用することも役立つ場合があります。直感はそれ以来です

    文字列 s には len(s)-q+1 個の q-gram があります

    と

    単一の編集操作は、最大 q-gram に影響を与えることができます。

    私たちはそれを推測することができます

    d の編集距離内にある文字列 s1 および s2 には、少なくとも max(len(s1),len(s2))-q+1-qk 一致する非位置 q-gram があります。

    最大編集距離 2 で「foobar」を検索する場合、一致する 7 文字の文字列 (「fotocar」など) には、少なくとも 2 つの一般的な 2 グラムが含まれている必要があります。

  3. 最後に、行うべき明らかなことは、 length でフィルタリングすることです。2 つの文字列間の編集距離は、少なくとも文字列の長さの差です。たとえば、しきい値が 2 で「foobar」を検索する場合、「foobarbar」は明らかに一致しません。

詳細および疑似 SQLについては、 http://pages.stern.nyu.edu/~panos/publications/deb-dec2001.pdfを参照してください。

于 2010-03-04T07:32:57.070 に答える
2

テーブル全体をスキャンする必要がないように、DNA q-gram のインデックス作成に関する興味深い論文:

www.comp.nus.edu.sg/~atung/publication/qgram_edit.pdf

于 2010-08-05T13:19:18.453 に答える