1

什么算法 - 似乎在域名停放页面上使用 - 需要一堆无空格的单词（例如“thecarrotofcurioity”）并或多或少正确地将其分解为组成词（例如“好奇的胡萝卜”）？

4

4 回答 4

2

从一个基本的Trie开始表示您的字典的数据结构。当您遍历字符串的字符时，使用一组指针而不是单个指针在 trie 中搜索您的方式 - 该组以 trie 的根为种子。对于每个字母，整个集合通过该字母指示的指针立即推进，如果一个集合元素不能由该字母推进，则将其从集合中移除。每当您到达一个可能的词尾时，就向集合中添加一个新的 root-of-trie（跟踪与该集合元素相关联的单词列表）。最后，一旦处理了所有字符，返回一个任意的单词列表，该列表位于特里树的根部。如果有多个，这意味着字符串可以以多种方式分解（例如“治疗师论坛”可以解析为 [“治疗师”，“

或者，在一个古怪的伪代码中（Java foreach，用括号表示的元组，用大括号表示的集合，使用 head :: tail 的cons，[] 是空列表）：

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;
 }

让我知道是否需要澄清或我遗漏了什么......

于 2009-08-05T05:13:32.293 回答
1

我想他们会像/usr/share/dict/words在您的普通或花园品种 Unix 系统上那样使用字典单词列表，并尝试查找单词匹配集（从左侧开始？），从而导致匹配覆盖的原始文本数量最多。一个简单的广度优先搜索实现可能会很好，因为它显然不需要运行得很快。

于 2009-08-04T23:16:20.077 回答
0

我想像这些网站做类似这样的事情：

  1. 获取目标语言的单词列表
  2. 删除“a”，“the”，...等“无用”词
  3. 遍历列表并检查哪些单词是域名的子字符串
  4. 取剩余列表中最常用的单词（或 AdSense 评分最高的单词，...）

当然，这会导致专家交流的废话，但是您还期望那里...

于 2009-08-04T23:37:11.737 回答
0

（免责声明：我自己没有尝试过，所以仅作为实验食品。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，那么你应该在原始字符串的那个位置插入一个空格。如果它小于零，那么你不应该。

如果您尝试它（或类似的东西）并且它对您有效（或无效），请在此处记下：-)

于 2009-08-05T00:23:31.247 回答