21

将字符串拆分为单词的正确方法是什么？（字符串不包含任何空格或标点符号）

例如：“stringintowords”->“String Into Words”

你能告诉我这里应该使用什么算法吗？

！更新：对于那些认为这个问题只是出于好奇的人。该算法可用于对域名（“sportandfishing .com”->“SportAndFishing .com”）进行大写，并且该算法目前被 aboutus dot org 用于动态执行此转换。

4

13 回答 13

23

假设您有一个函数isWord(w)，它使用字典检查是否w是一个单词。为简单起见，我们现在还假设您只想知道对于某些单词是否可以进行w这种拆分。这可以通过动态规划轻松完成。

让我们S[1..length(w)]成为一个带有布尔条目的表。S[i]如果单词w[1..i]可以拆分，则为真。然后设置S[1] = isWord(w[1])并计算for i=2length(w)

S[i] = (isWord[w[1..i] 或 {2..i} 中的任何 j：S[j-1] 和 isWord[j..i])。

如果字典查询是常数时间，这需要 O(length(w)^2) 时间。要真正找到拆分，只需将获胜拆分存储在每个设置为 true 的 S[i] 中。这也可以适用于通过存储所有此类拆分来枚举所有解决方案。

于 2010-08-12T15:16:23.383 回答
15

正如这里很多人提到的，这是一个标准的、简单的动态规划问题：Falk Hüffner 给出了最好的解决方案。附加信息：

(a) 您应该考虑使用 trie 实现isWord，如果您使用得当（即通过增量测试单词），这将为您节省大量时间。

(b) 输入“分段动态编程”会产生更详细的答案，来自大学级别的使用伪代码算法的讲座，例如杜克大学的这个讲座（甚至提供了一种简单的概率方法来处理什么当您的单词不会包含在任何字典中时执行）。

于 2010-08-12T23:48:18.653 回答
5

如果你想确保你做对了，你将不得不使用基于字典的方法，而且效率会非常低。您还必须期望从您的算法中收到多个结果。

例如：windowsteamblog（http://windowsteamblog.com/成名）

  • windows team blog
  • window steam blog
于 2010-08-12T11:21:58.663 回答
5

在这方面的学术文献中应该有相当多的内容。您要搜索的关键词是分词。例如，这篇论文看起来很有希望。

一般来说，您可能想了解马尔可夫模型和维特比算法。后者是一种动态编程算法，可以让您找到字符串的合理分段，而无需详尽地测试每个可能的分段。这里的基本见解是，如果您对前 m 个字符有 n 个可能的分段，并且您只想找到最有可能的分段，那么您不需要针对后续字符评估其中的每一个 - 您只需要继续评估最有可能的一个。

于 2010-08-12T11:35:12.230 回答
3

考虑给定字符串的可能拆分的绝对数量。如果n字符串中有字符，则n-1可能有分割的地方。例如，对于字符串cat，可以在 the 之前拆分，a也可以在 . 之前拆分t。这导致 4 种可能的分裂。

您可以将此问题视为选择需要拆分字符串的位置。您还需要选择拆分的数量。所以存在Sum(i = 0 to n - 1, n - 1 choose i)分裂的可能。根据二项式系数定理，x 和 y 都为 1，这等于 pow(2, n-1)。

当然，很多这种计算都依赖于常见的子问题，所以动态编程可能会加快你的算法。在我的脑海中，计算 aboolean matrix M such M[i,j] is true if and only if the substring of your given string from i to j is a word会很有帮助。您仍然有指数级的可能分割，但如果早期分割没有形成一个词，您将很快能够消除分割。一个解决方案将是一个整数序列 (i0, j0, i1, j1, ...)，条件为j sub k= i sub (k + 1)。

如果您的目标是正确的驼峰式 URL，我会回避这个问题并采取更直接的方法：获取 URL 的主页，从源 HTML 中删除所有空格和大写字母，然后搜索您的字符串。如果匹配，则在原始 HTML 中找到该部分并将其返回。您需要一个 NumSpaces 数组来声明原始字符串中出现了多少空格，如下所示：

Needle:       isashort    
Haystack:     This is a short phrase    
Preprocessed: thisisashortphrase   
NumSpaces   : 000011233333444444

你的答案将来自：

location = prepocessed.Search(Needle)
locationInOriginal = location + NumSpaces[location]
originalLength = Needle.length() + NumSpaces[location + needle.length()] - NumSpaces[location]
Haystack.substring(locationInOriginal, originalLength)

当然，如果 madduckets.com 在主页的某处没有“Mad Duckets”，这将会中断。唉，这就是你为避免指数问题而付出的代价。

于 2010-08-12T15:44:25.483 回答
1

这基本上是背包问题的变体，因此您需要的是完整的单词列表以及 Wiki 中涵盖的任何解决方案。

对于相当大的字典，这将是非常耗费资源和冗长的操作，您甚至无法确定这个问题是否会得到解决。

于 2010-08-12T11:14:07.760 回答
1

创建一个可能的单词列表，从长单词到短单词排序。

检查列表中的每个条目是否与字符串的第一部分相对应。如果相等，请将其删除并在您的句子中附加一个空格。重复这个。

于 2010-08-12T11:15:28.157 回答
1

这实际上可以在没有字典的情况下（在一定程度上）完成。本质上，这是一个无监督的分词问题。您需要收集大量域名，应用无监督分割学习算法（例如Morfessor）并将学习模型应用于新域名。不过，我不确定它的效果如何（但这会很有趣）。

于 2011-05-16T14:44:31.223 回答
1

其实，有了字典，这个问题就可以及时解决O(n)。更准确地说，(k + 1) * n在最坏的情况下，其中n是字符串中的字符数，k是字典中最长单词的长度。

此外，该算法允许您跳过垃圾。

这是我前段时间在 Common Lisp 中创建的工作实现：https ://gist.github.com/3381522

于 2013-01-02T19:52:30.277 回答
0

最好的办法是将 0 中的子字符串与字典进行比较，当您找到匹配项时，提取该单词并从该点开始新的字典搜索……但这很容易出错，而且您会复数和撇号（sinks、sink's）和其他词性有问题。

编辑

“singlemotion”会变成“singleemotion”还是“sing glee motion”？

于 2010-08-12T11:11:47.150 回答
0

将该字符串拆分为单词的唯一方法是使用字典。尽管这可能会占用大量资源。

于 2010-08-12T11:13:26.897 回答
0

我正在研究这个问题，并想也许我可以分享我是如何做到的。用文字解释我的算法有点太难了，所以也许我可以用伪代码分享我的优化解决方案：

string mainword = "stringintowords";
array substrings = get_all_substrings(mainword);

/** this way, one does not check the dictionary to check for word validity 
 *  on every substring; It would only be queried once and for all, 
 *  eliminating multiple travels to the data storage
 */
string query = "select word from dictionary where word in " + substrings;
array validwords = execute(query).getArray();

validwords = validwords.sort(length, desc);

array segments = [];
while(mainword != ""){
    for(x = 0; x < validwords.length; x++){
        if(mainword.startswith(validwords[x])) {
            segments.push(validwords[x]);
            mainword = mainword.remove(v);
            x = 0;
        }
    }

    /**
     * remove the first character if any of valid words do not match, then start again
     * you may need to add the first character to the result if you want to
     */
    mainword = mainword.substring(1);
}

string result = segments.join(" ");
于 2012-12-23T15:50:29.147 回答
0

一个运行时间为 O(n^2) 的简单 Java 解决方案。

public class Solution {
    // should contain the list of all words, or you can use any other data structure (e.g. a Trie)
    private HashSet<String> dictionary;

    public String parse(String s) {
        return parse(s, new HashMap<String, String>());
    }

    public String parse(String s, HashMap<String, String> map) {
        if (map.containsKey(s)) {
            return map.get(s);
        }
        if (dictionary.contains(s)) {
            return s;
        }
        for (int left = 1; left < s.length(); left++) {
            String leftSub = s.substring(0, left);
            if (!dictionary.contains(leftSub)) {
                continue;
            }
            String rightSub = s.substring(left);
            String rightParsed = parse(rightSub, map);
            if (rightParsed != null) {
                String parsed = leftSub + " " + rightParsed;
                map.put(s, parsed);
                return parsed;
            }
        }
        map.put(s, null);
        return null;
    }
}
于 2015-03-02T12:16:50.470 回答