给定一个搜索词列表，我如何知道我的字符串包含哪些搜索词？

有很多软件会采用搜索字符串并查找数据库中包含该字符串的所有文本（MySQL 的WHERE MATCH('searchterm', string_column)、谷歌等），但是有没有一个好的算法可以反其道而行之呢？

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

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

我有一个字符串，例如：

1962 年雪佛兰 Nova 敞篷车

有没有一个好的算法，我可以将列表和字符串放入其中，然后得到Chevy Nova out?

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

如果您要标记“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 Convertible”并将其转换为标记 (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”匹配两个标记，并且是最佳匹配，当然，确实如此。