1

我有一个带有标签的项目数据库，例如：

  • item1被标记为"pork with apple sauce"
  • item2被标记为"pork",
  • item3标记为"apple sauce"。

如果我匹配字符串：

“今天我想吃苹果酱猪肉，它会填饱我的”

对照标签，我会得到三个结果。但是，我只想获得最具体的，在这种情况下是item1.

这只是一个例子，我没有使用特定的数据库。只需在 ruby​​ 中进行字符串和映射。我想出了“模糊搜索”。我不确定这是否正确。有人可以建议如何解决这个特定问题吗？

4

4 回答 4

3

是的，您需要进行模糊匹配（又名近似匹配）。这是一个众所周知的问题，手动实现一个近似匹配算法并不是一件容易的事（但我相信它非常有趣！=D）。有很多因素会影响两个字符串 A 和 B 的“相似”程度，具体取决于您认为重要的事情，例如 A 在 B 中出现的次数，或者 A 中单词之间的顺序和距离有多近出现在 B 中，或者如果 A 中的“重要”词出现在 B 中，等等。

如果您可以使用现有的库，似乎有几个 Ruby gem 可以完成工作。例如，使用这个名为blur -string-match 的方法，它使用从 Lucene （一个 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 回答
2

根据您的具体用例，您可能不需要模糊搜索。

也许像这样一个非常基本的实现对你来说就足够了：

class Search
  attr_reader :items, :string

  def initialize(items, string)
    @items  = items
    @string = string.downcase
  end

  def best_match
    items.max_by { |item| rate(item) }
  end

  private

  def rate(item)
    tag_list(item).count { |tag| string.include?(tag) }
  end

  def tag_list(item)
    item[:tags].split(" ")
  end
end

 

items = [
  { id: :item1, tags: "pork with apple sauce" },
  { id: :item2, tags: "pork" },
  { id: :item3, tags: "apple sauce" }
]

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

Search.new(items, string).best_match
#=> {:id=>:item1, :tags=>"pork with apple sauce"}
于 2012-12-31T02:32:54.760 回答
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。

我会标记两个字符串，即针和干草堆，然后在计算发生次数的同时循环遍历它们。然后最后比较分数。

一些须藤代码：

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 回答