1

次のようなタグが付いたアイテムのデータベースがあります。

  • item1でタグ付けされています"pork with apple sauce"
  • item2でタグ付けされています"pork"、
  • item3でタグ付けされてい"apple sauce"ます。

文字列と一致する場合：

「今日はポークをアップルソースで食べたいのですが、いっぱいになります」

タグに対して、3つの結果が得られます。ただし、最も具体的なものを取得したいだけです。この場合はですitem1。

これは単なる例であり、特定のデータベースを使用していません。ルビーで文字列と地図を作成するだけです。「あいまい検索」を思いついた。これが正しいかどうかはわかりません。誰かがこの特定の問題を解決する方法を提案できますか？

4

4 に答える 4

3

はい、あいまい一致 (近似一致) を行う必要があります。これは非常によく知られた問題であり、おおよそのマッチング アルゴリズムを手動で実装するのは簡単なことではありません (しかし、非常に楽しいことは確かです! =D)。A と B の 2 つの文字列がどの程度「似ている」かは、B に A が何回出現するか、A の単語間の順序と距離がどれだけ近いかなど、重要と見なすものに応じて、さまざまな影響を与える可能性があります。 B に表示される場合、または A の「重要な」単語が B に表示される場合など。

既存のライブラリで何とかやってのけることができるなら、その仕事を成し遂げることができる Ruby gems がいくつかあるようです。たとえば、fuzzy-string-matchと呼ばれるこれを使用すると、Lucene (Java ライブラリの 1 つ) から移植されたJaro-Winkler 距離が使用されます。また、camelCased メソッド名の Java 規則も保持されているようです ¬¬):

require 'fuzzystringmatch'

matcher = FuzzyStringMatch::JaroWinkler.create(:pure)

tags = ["pork with apple sauce", "pork", "apple sauce"]
input = "Today I would like to eat pork with apple sauce, it would fill me up"

# Select the tag by distance to the input string (distance == 1 means perfect 
# match)
best_tag = tags.max_by { |tag| matcher.getDistance(tag, input) }

p best_tag

を正しく選択します"pork with apple sauce"。

また、他の多くの近似マッチング アルゴリズムを備えたamatchと呼ばれる他の gem もあります。

于 2012-12-31T02:09:27.113 に答える
1

データベース内のアイテム間の順序または特異性は、文字列と照合する前に決定されます。質問では明確にしていませんが、頭に入れているのは長さだと思います。したがって、データをハッシュとして持っているとします。

h = {
  item1: "pork with apple sauce",
  item2: "pork",
  item3: "apple sauce",
}

次に、これをタグの長さで並べ替えて、長いタグがリストの最初になるようにします。同時に、スペースの違いを気にする必要がないように、タグを正規表現に変換できます。次に、次のような配列があります。

a =
h
.sort_by{|_, s| s.length}.reverse
.map{|k, s| [k, Regexp.new("\\b#{s.gsub(/\s+/, '\\s+')}\\b")]}
# =>
# [
#   [
#     :item1,
#     /\bpork\s+with\s+apple\s+sauce\b/
#   ],
#   [
#     :item3,
#     /\bapple\s+sauce\b/
#   ],
#   [
#     :item2,
#     /\bpork\b/
#   ]
# ]

これを取得したら、文字列と一致するリスト内の最初の項目を見つけるだけです。

s = "Today I would like to eat pork with apple sauce, it would fill me up"

a.find{|_, r| s =~ r}[0]
# => :item1
于 2012-12-31T03:58:05.183 に答える
0

これは一般的なプログラミングに適用され、特にRubyには適用されません。

針と干し草の山の両方である両方の文字列をトークン化し、発生数をカウントしながら両方をループします。次に、最後にスコアを比較します。

いくつかのsudoコード：

needle[] = array of tokens from keysentence
haystack[] array of tokens from search string
int score = 0

do {
  haystackToken = haystack's next token

  do {
    needleToken = needle's next token

    if (haystackToken equals needleToken)
      score += 1

   } while(needle has more token)

} while (haystack has more tokens)
于 2012-12-31T01:30:11.050 に答える