如何将字符串拆分为单词。例如:“ stringintowords”->“将字符串转换成单词”?
nlp
5
0

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

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

您能否建议在这里使用哪种算法?

!更新:对于那些认为这个问题只是出于好奇的人。该算法可用于封装域名(“ sportandfishing.com”->“ SportAndFishing.com”),并且aboutus dot org当前使用此算法来动态进行此转换。

参考资料:
Stack Overflow
收藏
评论
共 5 个回答
高赞 时间 活跃

正如许多人在这里提到的那样,这是一个标准的,易于动态编程的问题:FalkHüffner提供了最佳解决方案。虽然附加信息:

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

(b)键入“分段动态编程”会产生更多更详细的答案,例如使用伪代码算法的大学级讲座,例如杜克大学的讲座 (甚至提供了一种简单的概率方法来处理什么)当您有任何词典中都不会包含的单词时执行该操作)。

收藏
评论

如果您想确保自己做对了, 必须使用基于字典的方法,这样的方法效率低下。您还必须期望从算法中收到多个结果。

例如: windowsteambloghttp://windowsteamblog.com/fame的

  • windows team blog
  • window steam blog
收藏
评论

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

S[1..length(w)]为带有布尔条目的表。如果单词w[1..i]可拆分,则S[i]为true。然后设置S[1] = isWord(w[1])for i=2设置length(w)

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

如果字典查询是恒定时间,则需要O(length(w)^ 2)时间。要实际找到拆分,只需将获胜的拆分存储在设置为true的每个S [i]中。也可以通过存储所有此类拆分来枚举所有解决方案。

收藏
评论

关于这一点,学术文献中应该有很多。您要搜索的关键词是分 。例如, 本文看起来很有希望。

通常,您可能需要学习markov模型viterbi算法 。后者是一种动态编程算法,可以使您找到字符串的合理分段,而无需详尽测试每个可能的分段。此处的基本见解是,如果对前m个字符有n个可能的细分,并且只想找到最可能的细分,则无需针对后续字符对每个细分进行评估-您只需要继续评估最可能的一个。

收藏
评论

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

您可以在选择需要在何处分割字符串时查看此问题。您还需要选择将要拆分的数量。因此,存在Sum(i = 0 to n - 1, n - 1 choose i)可能的分裂。根据二项系数定理 ,x和y均为1,这等于pow(2,n-1)。

当然,很多这种计算都基于常见的子问题,因此动态编程可能会加快算法的速度。在我的脑海中,计算boolean 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”,这种情况就会中断。 las,这就是您避免出现指数问题所需付出的代价。

收藏
评论
新手导航
  • 社区规范
  • 提出问题
  • 进行投票
  • 个人资料
  • 优化问题
  • 回答问题

关于我们

常见问题

内容许可

联系我们

@2020 AskGo
京ICP备20001863号