2

有很多软件会使用搜索字符串并在数据库中找到包含它的所有文本（MySQL WHERE MATCH('searchterm', string_column)、Google 等），但是有没有好的算法可以反过来呢？

假设我有一个搜索词列表：

丰田普锐斯、丰田塔科马、本田思域、雪佛兰 Nova、雪佛兰 Volt

我有一个字符串，比如：

1962 年雪佛兰 Nova 敞篷车

有没有一个好的算法可以让我把列表和字符串放进去，然后Chevy Nova出去？

如果它们都易于标记，我可以标记它们并进行内部连接，但我对我无法分辨输入字符串的哪一部分是“重要”部分的情况感兴趣。

4

1 回答 1

3

如果您要对“1962 Chevy Nova 敞篷车”[原文如此] 进行标记，您最终会得到四个足够重要或有趣的标记。如果您正在跟踪您的语言中所有可能的单词，那么您将拥有每个单词的索引。

另一方面，你有你的搜索词。在每种情况下，您都对有趣的单词进行了标记和索引。每一个都可以看作是一对两个令牌索引。

那么，如果您接受输入并寻找匹配的搜索词，您会问哪些搜索词具有输入的任何词？

因为我本质上是一个数据库专家，所以我可以想象像这样创建令牌列表：

CREATE TABLE aa_tokens (
  id INT NOT NULL AUTO_INCREMENT PRIMARY KEY ,
  word VARCHAR( 40 ) NOT NULL 
);

insert into aa_tokens (word) values
  ('1962'),           -- 1
  ('Chevy'),          -- 2
  ('Civic'),          -- 3
  ('Honda'),          -- 4
  ('Nova'),           -- 5
  ('Prius'),          -- 6
  ('Tacoma'),         -- 7
  ('Toyota'),         -- 8
  ('Volt'),           -- 9
  ('convertable');    -- 10

和一个搜索表，以便每个搜索都有一个 id：

CREATE TABLE aa_search (
  id INT NOT NULL AUTO_INCREMENT PRIMARY KEY ,
  text VARCHAR( 255 ) NOT NULL
);

insert into aa_search (text) values
  ('Toyota Prius'),   -- 1
  ('Toyota Tacoma'),  -- 2
  ('Honda Civic'),    -- 3
  ('Chevy Nova'),     -- 4
  ('Chevy Volt');     -- 5

然后是一个组合搜索和标记的表：

CREATE TABLE aa_searchToks (
  search INT NOT NULL,
  token INT NOT NULL
);

insert into aa_searchToks (search, token) values
  (1, 8),
  (1, 6),
  (2, 8),
  (2, 7),
  (3, 4),
  (3, 3),
  (4, 2),
  (4, 5),
  (5, 2),
  (5, 9);

现在，如果我们将输入字符串“1962 Chevy Nova convertable”转换为标记（1、2、5、10），我们可以进行查询以查看搜索词的标记：

select search, count(*) from aa_searchToks
  where token in (1, 2, 5, 10) group by search;

结果是：

+--------+----------+
| search | count(*) |
+--------+----------+
|      4 |        2 |
|      5 |        1 |
+--------+----------+

或查询有点不同：

select search, (select text from aa_search s where st.search = s.id) as text, 
  count(*) from aa_searchToks st where token in (1, 2, 5, 10) group by search;

导致：

+--------+------------+----------+
| search | text       | count(*) |
+--------+------------+----------+
|      4 | Chevy Nova |        2 |
|      5 | Chevy Volt |        1 |
+--------+------------+----------+

我们可以看到“Chevy Nova”匹配两个标记并且是最佳匹配，当然，它是。

于 2012-04-07T17:13:35.463 回答