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

Question

有很多软件可以使用搜索字符串并在您的数据库中找到包含它的所有文本(MySQL 的 WHERE MATCH('searchterm', string_column) 、Google 等)，但是有没有一种好的算法可以反其道而行之？

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

Toyota Prius, Toyota Tacoma, Honda Civic, Chevy Nova, Chevy Volt

我有一个字符串，例如:

1962 Chevy Nova convertable

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

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

Answer 1

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

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

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

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

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”匹配两个标记并且是最佳匹配，当然，它是。