解析连续字符串中的单词

本文关键字：单词 字符串 连续 | 更新日期: 2023-09-27 17:59:29

如果有一个包含单词而没有空格的字符串，那么在我有一个字典/列表包含这些单词的情况下，我应该如何解析这些单词？

例如，如果我的字符串是"thisisstringwithwords"，我如何使用字典创建输出"thisisa string with words"？

我听说使用数据结构Tries可能会有所帮助，但如果有人能帮助处理伪代码呢？例如，我在想，也许你可以把字典索引到一个trie结构中，然后把每个字符放在trie后面；问题是，我不熟悉如何在（伪）代码中做到这一点。

解析连续字符串中的单词

我假设您想要一个有效的解决方案，而不是一个明显的解决方案——您可以反复检查文本是否以词典单词开头。

如果字典足够小，我想你可以尝试修改标准的KMP算法。基本上，在字典上构建一个有限状态机，它逐个字符地消耗文本并生成构造的单词。

编辑：我似乎在重新尝试。

我已经做了类似的事情。你不能用一本简单的字典。结果会很混乱。这取决于你只需要做一次还是整个程序。

我的解决方案是：

  1. 通过工作连接到数据库字典列表中的单词（用于在线词典示例）
  2. 过滤字典中的长单词和短单词，并检查是否要修剪内容（例如，不要使用只有一个字符的单词，如"I"）
  3. 从短单词开始，将bigString与数据库词典进行比较

现在您需要创建一个"可能性表"。因为很多单词都是100%的，但都是错误的。这个词越长，你就越确信这个词是正确的

它是cpu密集型的，但它可以精确地工作。比方说，您使用的是一个包含10000个单词的小词典，其中3000个单词的长度为8个字符，您需要将开头的bigString与所有3000个单词进行比较，只有找到结果，才允许继续下一个单词。如果你的bigString中有200个字符，你需要大约（2000个字符/8个平均字符）=250个完整循环（带比较）。

对我来说，我还对拼写错误的单词进行了一个小的比较验证。

程序示例（不要复制粘贴）

    Dim bigString As String = "helloworld.thisisastackoverflowtest!"
    Dim dictionary As New List(Of String) 'contains the original words. lets make it case insentitive
    dictionary.Add("Hello")
    dictionary.Add("World")
    dictionary.Add("this")
    dictionary.Add("is")
    dictionary.Add("a")
    dictionary.Add("stack")
    dictionary.Add("over")
    dictionary.Add("flow")
    dictionary.Add("stackoverflow")
    dictionary.Add("test")
    dictionary.Add("!")

    For Each word As String In dictionary
        If word.Length < 1 Then dictionary.Remove(word) 'remove short words (will not work with for each in real)
        word = word.ToLower 'make it case insentitive
    Next
    Dim ResultComparer As New Dictionary(Of String, Double) 'String is the dictionary word. Double is a value as percent for a own function to weight result
    Dim i As Integer = 0 'start at the beginning
    Dim Found As Boolean = False
    Do
        For Each word In dictionary
            If bigString.IndexOf(word, i) > 0 Then
                ResultComparer.Add(word, MyWeightOfWord) 'add the word if found, long words are better and will increase the weight value 
                Found = True
            End If
        Next
        If Found = True Then
            i += ResultComparer(BestWordWithBestWeight).Length
        Else
            i += 1
        End If
    Loop

我告诉过你，这似乎是一项不可能完成的任务。但你可以看看这个相关的SO问题，它可能会对你有所帮助。

如果你确定你在字典里有这个短语的所有单词，你可以使用这个算法：

String phrase = "thisisastringwithwords";
String fullPhrase = "";
Set<String> myDictionary;
do {
    foreach(item in myDictionary){
        if(phrase.startsWith(item){
            fullPhrase += item + " ";
            phrase.remove(item);
            break;
        }
    }
} while(phrase.length != 0);

有很多复杂的问题，比如，有些项目的开头是相等的，所以代码将被更改为使用一些树搜索、BST等。

这正是在试图以编程方式解析像中文这样单词之间没有空格的语言时遇到的问题。一种适用于这些语言的方法是从标点符号上分割文本开始。这会给你短语。接下来，你对短语进行迭代，并尝试将它们分解为单词，从字典中最长单词的长度开始。假设长度为13个字符。取短语中的前13个字符，看看它是否在你的字典里。如果是，现在就把它当作一个正确的单词，在短语中继续前进并重复。否则，将子字符串缩短为12个字符，然后再缩短为11个字符，以此类推。

这非常有效，但并不完美，因为我们不小心对第一位的单词产生了偏见。消除这种偏见并仔细检查结果的一种方法是从短语末尾开始重复这个过程。如果你得到了相同的单词break，你可能会称之为good。如果没有，你有一个重叠的单词段。例如，当你解析从末尾开始的示例短语时，你可能会得到（向后强调）

words with string a Isis th

起初，伊西斯（埃及女神）这个词似乎是正确的。然而，当你发现字典里没有"th"时，你就知道附近有分词问题。由于两个单词都在字典中，因此通过对未对齐的序列"thisis"进行正向分割结果"thiis"来解决此问题。

这个问题的一个不太常见的变体是相邻单词共享一个序列，该序列可以是任意一种。如果你有一个像"archand"这样的序列（用来编造一些东西），它应该是"arc-hand"还是"arch-and"？确定的方法是对结果应用语法检查器。无论如何，这应该对全文进行。

好的，我将对此做一个波浪形的尝试。对于您的问题，完美的（ish）数据结构是由字典中的单词组成的（正如您所说的trie）。trie最好被想象成DFA，一个很好的状态机，你可以在每个新角色上从一个状态转到下一个状态。这在代码中真的很容易做到，Java（ish）风格的类应该是：

Class State 
{
   String matchedWord;
   Map<char,State> mapChildren;
}

从那时起，构建trie就很容易了。这就像有一个有根的树结构，每个节点都有多个子节点。每个孩子都会在一个角色转换中被访问。HashMap类结构的使用缩短了查找字符到下一个State映射的时间。或者，如果你的字母表只有26个字符，那么fixed size array of 26也可以。

现在，假设所有这些都有意义，你有一个trie，你的问题仍然没有完全解决。这就是你开始做正则表达式引擎所做的事情的地方，沿着trie走下去，跟踪与字典中的一个完整单词匹配的状态（这就是我在State结构中使用matchedWord的原因），如果当前的线索遇到死胡同，使用一些回溯逻辑跳到以前的匹配状态。我知道它的一般性，但考虑到trie结构，其余的都相当简单。

如果你有单词词典，并且需要快速实现，假设词典查找为O（1），那么可以在O（n^2）时间内通过动态编程有效地解决这个问题。下面是一些C#代码，可以改进子字符串提取和字典查找。

public static String[] StringToWords(String str, HashSet<string> words)
{      
  //Index of char - length of last valid word
  int[] bps = new int[str.Length + 1];
  for (int i = 0; i < bps.Length; i++)      
    bps[i] = -1;
  for (int i = 0; i < str.Length; i++)
  {
    for (int j = i + 1; j <= str.Length ; j++)
    {
      if (bps[j] == -1)
      {
        //Destination cell doesn't have valid backpointer yet
        //Try with the current substring
        String s = str.Substring(i, j - i);
        if (words.Contains(s))
          bps[j] = i;
      }
    }        
  }      
  //Backtrack to recovery sequence and then reverse 
  List<String> seg = new List<string>();
  for (int bp = str.Length; bps[bp] != -1 ;bp = bps[bp])      
    seg.Add(str.Substring(bps[bp], bp - bps[bp]));      
  seg.Reverse();
  return seg.ToArray();
}

使用/usr/share/dict/words中的单词列表构建hastset并使用进行测试

foreach (var s in StringSplitter.StringToWords("thisisastringwithwords", dict))
    Console.WriteLine(s);

我得到的输出是"t hi sis a string with words"。因为正如其他人所指出的，该算法将返回有效的分割（如果存在），但这可能不是您期望的分割。短单词的存在降低了分割质量，如果两个有效的子分割进入一个元素，则可以添加启发式来支持较长的单词。

有更复杂的方法，即有限状态机和语言模型，可以生成多个分段并应用概率排序。

相关文章：