快速和有效的算法为短语字典查找

Question

假设我有一本字典，里面有几百万个单词和短语。对于每个输入句子，我想识别(精确匹配)字典中包含的所有单词/短语。应该优先使用最长的字典名称，并且没有重叠。例如:

Sentence: "Los Angeles Lakers visited Washington State last week"
Dictionary: {Los Angeles, Lakers, Los Angeles Lakers, Washington, State, Washington State University}
Then the sentence would be tagged as follows:
[Los Angeles Lakers] visited [Washington] [State] last week. 

我能想到的一个解决方案是将字典存储在内存中，并使用恒定的查找时间(例如，基于散列的集合)，然后从每个句子中提取所有单词n-gram (n可以设置为字典中最长短语中的单词数)，并将每个单词与字典进行比较，并保留最长的不重叠的单词。有没有更好的解决方案?(因为n-gram的生成可能很慢)。也许树木能帮上忙?

谢谢!

Answer 1

您可能想要考虑像基数树或前缀树这样的东西，使用整个单词作为构建的一部分。这些树对于字典类型的问题来说是很自然的。

然后简单地将事物分成单词，并对树进行搜索。根据分组的预期长度，您可以从前面(不情愿)或从后面(贪婪)构建。

Answer 2

您可以查看DAWG(有向无循环词图)。您可以将整个短语存储为DAWG中的路径。然后，您将开始匹配句子并找到匹配的最长短语作为最长路径。然后，您将以类似的方式继续处理其余不匹配的句子。空白区域需要一些特殊处理。

Answer 3

以下代码执行句子的非重叠标记，优先考虑较长的匹配。

它将句子视为字符串标记数组。

它使用"max_key_size"参数(字典中键的最大大小)来避免搜索永远不会发生的匹配。在您的示例中，生成的句子是:

[[洛杉矶湖人队]，访问，[华盛顿]，[州]，最后，一周]

希望有帮助:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
public class NonOverlappingTagging {
    private static ArrayList non_overlapping_tagging(String[] sentence, HashMap dict,int max_key_size) {
        ArrayList tag_sentence = new ArrayList();
        int N = sentence.length;
        if (max_key_size == -1) {
            max_key_size = N;
        }
        int i = 0;
        while (i < N) {
            boolean tagged = false;
            int j = Math.min(i + max_key_size, N); //avoid overflow
            while (j > i) {
                String[] literal_tokens = Arrays.copyOfRange(sentence, i, j);
                String literal = join(literal_tokens, " ");
                System.out.println(literal);
                if (dict.get(literal) != null) {
                    tag_sentence.add("["+literal+"]");
                    i = j;
                    tagged = true;
                }
                else {
                    j -= 1;
                }
            }
            if (!tagged) {
                tag_sentence.add(sentence[i]);
                i += 1;
            }
        }
        return tag_sentence;
    }
    private static String join(String[] sentence, String separator) {
        String result = "";
        for (int i = 0; i < sentence.length; i++) {
            String word = sentence[i];
            result += word + separator;
        }
        return result.trim();
    }
    public static void main(String[] args) {
        String[] sentence = {"Los", "Angeles", "Lakers", "visited", "Washington", "State", "last", "week"};
        HashMap <String, Integer>dict = new HashMap();
        dict.put("Los Angeles", 1);
        dict.put("Lakers", 1);
        dict.put("Los Angeles Lakers", 1);
        dict.put("Washington", 1);
        dict.put("State", 1);
        dict.put("Washington State University", 1);
        ArrayList tagging = non_overlapping_tagging(sentence, dict, -1);
        System.out.println(tagging);    
    }   
}