4

この問題について助けが必要です:

入力として、のような文字列があります。または、他の単語の順列にBlue cat green eyes 2342342することもできます。Cat blue eyes green 23242

私のDBテーブルにはいくつかのデータがあります。列の 1 つは、たとえばキーワードと呼ばれます。

このテーブルの例を次に示します。

ここに画像の説明を入力

私の仕事は、入力文字列のいくつかの単語に一致する、DB テーブルの列 KEYWORDS でレコードを見つけることです。

例: 文字列" Blue cat green eyes 2342342" " Cat blue eyes green 23242"および" Cat 23242 eyes blue green"の場合、結果は"blue cat" (テーブルの最初の行) になります。このタスクを解決する方法を想像できる唯一の方法は次のようになります。

  1. 文字列から一貫してすべての単語を取得します。
  2. %like%このすべての単語を表の列で検索します。
  3. 見つからない場合は、この単語がキーではなく、関心がないことを意味します。
  4. 一度見つかったら - すごい！間違いなく、これが私たちが探しているものです。
  5. 複数の結果がある場合:
  6. まだテストされていない文字列のすべての単語から、一貫してすべての単語を取得します。
  7. %like%ステップ 2 の結果でこの単語を検索します。
  8. など…</li>

このアルゴリズムのグラフィカルなスキーマはこちら

ただし、テーブルに多数のレコードがあり、入力文字列が多数の単語で構成されている場合、このアルゴリズムの動作は非常に遅くなるようです。

だから、私の質問は次のとおりです。このタスクを解決するのに役立つ特別なアルゴリズムはありますか?

4

2 に答える 2

4

次のような別のテーブルを採用できます

ID    KeywordID     Word
1     1             blue
2     2             blue
3     1             cat

文字列を変換します

"Blue cat green eyes 2342342"

一連のインデックスとカウント:

SELECT KeywordID, COUNT(*) FROM ancillary WHERE Word IN ('blue','cat','green','eyes'...)

これは、一連の完全一致を実行して、たとえば、次のように返します。

KeywordID   Count
1           2
2           1

次に、ID 1 のキーワード グループには 2 つの単語があることがわかります。つまり、カウント 2 はそれらすべてに一致することを意味します。したがって、keywordid 1 は満たされます。グループ 2 にも 2 つの単語 (black、cat) がありますが、見つかったのは 1 つだけで、一致はありますが完全ではありません。

キーワード ID と一緒にキーワード セットのサイズも記録すると、同じ ID のすべてのキーワードが同じ KeywordSize になり、GROUP BY もできます。

KeywordID   KeywordSize    Count
1           2              2
2           2              1

SELECT COUNT(*)/KeywordSize AS match ... ORDER BY matchまた、キーワードの一致を関連性でソートすることもできます。

もちろん、KeywordID を取得すると、キーワード テーブルで見つけることができます。

実装

キーワード リスト「黒猫」を既存のテーブルに追加します。

したがって、このキーワード リストを単語に分解すると、「黒」、「怒り」、「猫」が得られます。

通常、キーワード リストを既存のテーブルに挿入し、新しく作成された行の ID を取得します。たとえば、1701 とします。

ここで、"ancillary" と呼ばれる新しいテーブルに単語を挿入します。このテーブルには、プライマリ テーブルのキーワード行 ID、単一の単語、およびその単語の単語リストのサイズのみが含まれます。

テーブル行 1701 に全部で 3 つの単語を挿入することがわかっているので、size=3 で、これらのタプルを挿入します。

(1701, 3, 'black')
(1701, 3, 'cat')
(1701, 3, 'angry')

(これらは独自の一意の ID を受け取りますが、これは私たちには関係ありません)。

しばらくして、次の文を受け取ります。

'Schroedinger cat is black and angry'

最初に、「is」や「and」など、削除するヌル単語のリストに対してクエリを実行できます。しかし、これは必要ありません。

次に、単語と同じ数のクエリを実行して、「Schroedinger」を含む行がどこにもないことを発見し、それを削除できます。しかし、これも必要ではありません。

最後に、補助に対する実際のクエリを作成します。

SELECT KeywordID, COUNT(*) AS total, ListSize*100/COUNT(*) AS match
    FROM ancillary WHERE Word IN ('Schroedinger','cat','is','black','and','angry')
    GROUP BY KeywordID;

はWHERE、たとえば次の行を返します。

(1234, 'black') -- from 'black cat'
(1234, 'cat')   -- from 'black cat'
(1423, 'angry') -- from 'angry birds'
(1701, 'cat')   -- from 'black angry cat'
(1701, 'angry') -- from 'black angry cat'
(1701, 'black') -- from 'black angry cat'
(1999, 'cat')   -- from 'nice white cat'

そのため、GROUP はKeywordIDこれらの行のカーディナリティを返します。

1423   1   50%
1701   3  100%
1234   2  100%
1999   1   33%

これで、一致率の降順で並べ替え、次にリスト サイズの降順で並べ替えることができます (3 つの単語の 100% の一致は 2 つの単語の 100% の一致よりも優れており、2 つの単語の 1 つに一致することは 3 つの単語の 2 つに一致することよりも優れているため):

1701   3  100% -- our best match
1234   2  100% -- second runner
1423   1   50%
1999   1   33%

一致率を追加して、1 つのクエリで最初のテーブルを取得することもできます。

SELECT mytable.*, total, match FROM
mytable JOIN (
SELECT KeywordID, COUNT(*) AS total, ListSize*100/COUNT(*) AS match
    FROM ancillary WHERE Word IN ('Schroedinger','cat','is','black','and','angry')
    GROUP BY KeywordID
) AS ancil ON (mytable.KeywordID = ancil.KeywordID)
ORDER BY match DESC, total DESC;

最大のコストは、Word列にインデックスを付ける必要がある「補助」の完全一致です。

于 2012-10-26T11:54:03.033 に答える
1

スフィンクスのような全文検索エンジンを見たいと思うかもしれません: http://sphinxsearch.com/

または、別の方法 - ストアド プロシージャを作成し、指定されたセパレータを使用して検索文字列をキーワードに分割し、DB 列の各キーワードの charindex を探します (データベース管理システムによって異なります)。

于 2012-10-26T11:12:53.713 に答える