分词算法

Question

似乎在域名停放页面上使用的算法是什么？它采用一堆无空格的单词（例如“thecarrotofcuriosity”）并或多或少正确地将其分解为组成词（例如“the carrot ofurious”）？

Answer 1

从表示字典的基本 Trie 数据结构开始。 当您迭代字符串的字符时，请使用一组指针而不是单个指针在 trie 中搜索 - 该集合以 trie 的根为种子。 对于每个字母，整个集合通过该字母指示的指针立即前进，如果集合元素不能通过该字母前进，则将其从集合中删除。 每当到达可能的词尾时，就向集合中添加一个新的 trie 根（跟踪与该集合元素关联的单词列表）。 最后，处理完所有字符后，返回位于 trie 根的任意单词列表。 如果有多个，则意味着该字符串可以以多种方式分解（例如“therapyforum”可以解析为 [“therapy”, “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;
 }

如果我需要澄清或者我错过了什么，请告诉我......

Answer 2

我想他们会在你的普通或普通的 Unix 系统上获取像 /usr/share/dict/words 这样的字典单词列表，并尝试找到结果的单词匹配集（从左边开始？）匹配所覆盖的最大量的原始文本。 一个简单的广度优先搜索实现可能会很好地工作，因为它显然不需要运行得很快。

Answer 3

我想象这些网站会这样做：

1. 获取目标语言的单词列表
2. 删除“无用”单词，例如“a”，“the”，...
3. 运行列表并检查哪些单词是子字符串域名的
4. 取剩余列表中最常见的单词（或者具有最高 Adsense 评级的单词，...）

当然，这对 ExpertExchange 来说是无意义的，但是您还能期待什么...

Answer 4

（免责声明：我自己没有尝试过，所以仅将其作为实验用的食物。4克大多是从蓝天中取出的，只是根据我的经验，3克效果不太好；5-克或更多可能效果更好，即使您必须处理相当大的桌子）。 从某种意义上说，它也很简单，因为它没有考虑字符串的结尾 - 如果它对你有用，否则你可能需要考虑修复结尾。

该算法将在可预测的时间内运行，该时间与您尝试拆分的字符串的长度成正比。

所以，首先：获取大量人类可读的文本。 对于每个文本，假设它在单个字符串 str 中，运行以下算法（伪代码式表示法，假设 [] 是类似哈希表的索引，并且不存在的索引返回 '0 ')：

for(i=0;i<length(s)-5;i++) {
  // take 4-character substring starting at position i
  subs2 = substring(str, i, 4); 
  if(has_space(subs2)) {
    subs = substring(str, i, 5);
    delete_space(subs);
    yes_space[subs][position(space, subs2)]++;
  } else {
    subs = subs2;
    no_space[subs]++;
  }
}

这将为您构建表格，帮助您决定给定的 4-gram 是否需要在其中插入空格。

然后，将字符串拆分，我将其表示为 xstr，然后执行以下操作：

for(i=0;i<length(xstr)-5;i++) {
  subs = substring(xstr, i, 4);
  for(j=0;j<4;j++) {
    do_insert_space_here[i+j] -= no_space[subs];
  }
  for(j=0;j<4;j++) {
    do_insert_space_here[i+j] += yes_space[subs][j];
  }
}

然后，您可以遍历“do_insert_space_here[]”数组 - 如果元素位于给定位置大于0，那么你应该在原始字符串的该位置插入一个空格。 如果它小于零，那么你不应该这样做。

如果您尝试它（或类似的东西）并且它对您有用（或不起作用），请在此处留言:-)