algorithm - 分词算法

Question

什么是算法 - 似乎在域停放页面上使用 - 接受一堆没有空格的词(例如“thecarrotofcuriosity”)并或多或少正确地将其分解为组成词(例如“好奇的胡萝卜” “)？

Answer 1

从基础开始Trie表示字典的数据结构。当您遍历字符串的字符时，使用一组指针而不是单个指针在 trie 中搜索您的方式 - 该集合以 trie 的根作为种子。对于每个字母，整个集合通过该字母指示的指针立即前进，如果一个集合元素不能通过该字母前进，则将其从集合中移除。每当您到达可能的单词结尾时，向集合中添加一个新的树根(跟踪与该集合元素相关联的单词列表)。最后，处理完所有字符后，返回一个任意单词列表，该列表位于树的根部。如果不止一个，这意味着字符串可以通过多种方式分解(例如“therapistforum”可以解析为 [“therapist”，“forum”] 或 [“the”，“rapist”，“forum” ]) 并且它是未定义的，我们将返回它。

或者，在一个搞笑的伪代码中(Java foreach，用圆括号表示的元组，用大括号表示的集合，cons 使用 head::tail，[] 是空列表):

List<String> breakUp(String str, Trie root) {
    Set<(List<String>, Trie)> set = {([], root)};
    for (char c : str) {
        Set<(List<String>, Trie)> newSet = {};
        for (List<String> ls, Trie t : set) {
            Trie tNext = t.follow(c);
            if (tNext != null) {
                newSet.add((ls, tNext));
                if (tNext.isWord()) {
                    newSet.add((t.follow(c).getWord() :: ls, root));
                }
            }
        }
        set = newSet;
     }
     for (List<String> ls, Trie t : set) {
        if (t == root) return ls;
     }
     return null;
 }

如果我需要澄清或遗漏了什么，请告诉我...