1

我有一个有趣的问题需要帮助。我目前正在研究我的程序的一个功能并偶然发现了这个问题

  1. 我有一个巨大的印度尼西亚街道名称列表（> 100k 行）存储在数据库中，每个街道名称可能有超过 1 个单词。例如：“Sudirman”、“Gatot Subroto”或“Jalan Asia Afrika”都是合法的街道名称

  2. 在数据库中有一堆文本（> 100 万行），我将它们分成句子。现在，我需要做的功能（确切地说是功能）是测试句子中是否有街道名称，所以只是一个真/假测试

    我试图通过执行以下步骤来解决它：

一个。将街道名称放入 Key,Value Hash

湾。将每个句子分成单词

C。测试单词是否在哈希中

这很快，但不适用于多个单词

我想到的另一种选择是执行以下步骤：

一个。将每个句子分成单词

湾。使用 LIKE 语句查询数据库（即 SELECT #### FROM street_table WHERE name like '%word%' ）

C。如果查询返回一行，则表示该句子包含街道名称

现在，这个解决方案将是一个非常密集的 IO。

所以我的问题是“做这个测试最有效的方法是什么”？与编程语言无关。我主要在 python 中执行此操作，但只要我能掌握概念，任何语言都可以

============编辑1 =================

这会是定期的吗？

是的，我会以 1 分钟的间隔调用这个特性/功能。每个调用至少需要 100 行文本，并根据街道名称数据库对其进行测试

4

4 回答 4

2

一个简单的解决方案是使用第一个街道名称=>完整街道名称创建字典/多重映射。当您迭代句子中的每个单词时，您将查找潜在的街道名称，并检查您是否有匹配项（通过查看下一个单词）。

该算法应该相当容易实现，并且性能也应该相当不错。

于 2012-06-11T12:00:21.083 回答
1

使用 nlp，您可以确定句子中的专有名词。请参考以下链接。

http://nlp.stanford.edu/software/lex-parser.shtml

斯坦福解析器的计算是准确的。一旦你有了专有名词，你就可以决定要遵循的方法。

于 2012-06-11T11:53:10.787 回答
0

因此，您有一个文档并想要搜索它是否包含您的任何街道名称列表？

Turbo Boyer-Moore 是一个很好的起点。

这是有关涡轮增压器摩尔的更多信息

但是，我坚信，您将不得不对街道名称列表的组织做一些事情。应该有一些桶访问它，即您可以轻松过滤街道名称：

这里是一个例子：街道名称：Asia-Pacific-street

您可以通过以下方式访问您的列表： A（获取所有以 A 开头的起点） AS（获取所有以 AS 开头的起点）

等等...

我相信你应该有很多桶，至少 26（第一个字母）* 26（第二个字母）

有关分桶的更多信息

于 2012-06-11T11:51:42.227 回答
0

Aho-Corasick 算法可能非常有用。它的优点之一是它的运行时间与您正在搜索的单词数量无关（仅与您搜索的文本时间无关）。如果您的街道名称列表不经常更改，它将特别有用。

http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm

于 2012-06-14T22:09:00.627 回答