如果 a 有一个包含单词且没有空格的字符串，鉴于我有一个包含这些单词的字典/列表，我应该如何解析这些单词？
例如，如果我的字符串是“thisisastringwithwords”，我如何使用字典来创建输出“这是一个带单词的字符串”？
我听说使用数据结构Tries可能会有所帮助，但也许有人可以帮助处理伪代码？例如，我在想也许你可以将字典索引到一个 trie 结构中，然后沿着 trie 中的每个字符；问题是，我不熟悉如何在（伪）代码中执行此操作。
问问题
2055 次
7 回答
1
我已经做了类似的事情。您不能使用简单的字典。结果会很乱。这取决于您是否只需执行一次或作为整个程序执行此操作。
我的解决方案是：
- 使用字典列表（例如在线字典）中的工作词连接到数据库
- 过滤字典中的长词和短词并检查是否要修剪内容（例如，不要使用只有一个字符的词，例如'I'）
- 从简短的单词开始，将您的 bigString 与数据库字典进行比较。
现在您需要创建一个“可能性表”。因为很多词可以100％适应但都是错误的。你越确定这个词越长，这个词就是正确的。
它是 cpu 密集型的，但它可以在结果中精确地工作。因此，假设您正在使用一个包含 10,000 个单词的小字典，其中 3,000 个单词的长度为 8 个字符，您需要在开始时将您的 bigString 与所有 3,000 个单词进行比较，并且只有找到结果后，才允许继续下一个词。如果您的 bigString 中有 200 个字符，则您需要大约 (2000chars / 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
于 2011-06-20T08:09:25.587 回答
0
这就是在尝试以编程方式解析诸如中文之类的语言时遇到的确切问题，其中单词之间没有空格。一种适用于这些语言的方法是首先在标点符号上拆分文本。这给了你短语。接下来，您遍历短语并尝试将它们分解为从字典中最长单词的长度开始的单词。假设长度为 13 个字符。从短语中取出前 13 个字符，看看它是否在您的字典中。如果是这样，现在把它当作一个正确的词，在短语中前进并重复。否则，将子字符串缩短为 12 个字符，然后是 11 个字符，以此类推。
这非常有效，但并不完美，因为我们不小心对首先出现的单词产生了偏见。消除这种偏见并仔细检查结果的一种方法是从短语末尾开始重复该过程。如果你得到相同的单词中断，你可能会称之为好。如果没有，你有一个重叠的词段。例如，当您从末尾开始解析示例短语时，您可能会得到（向后强调）
words with string a Isis th
起初，Isis（埃及女神）这个词似乎是正确的词。但是，当您发现“th”不在您的字典中时，您就知道附近存在分词问题。通过使用未对齐序列“thisis”的前向分割结果“thisis”来解决这个问题，因为这两个词都在字典中。
这个问题的一个不太常见的变体是当相邻的单词共享一个可以去任何方向的序列时。如果你有一个像“archand”（编造一些东西）这样的序列，它应该是“arc hand”还是“arch and”？确定的方法是对结果应用语法检查器。无论如何，这应该对整个文本进行。
于 2011-06-20T14:15:40.703 回答
0
如果您有单词字典并且需要快速实现，则可以在 O(n^2) 时间内通过动态编程有效地解决此问题，假设字典查找为 O(1)。下面是一些 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”。因为正如其他人指出的那样，该算法将返回有效的分段（如果存在），但这可能不是您期望的分段。短词的存在降低了分割质量，如果两个有效的子分割进入一个元素，您可能可以添加启发式来支持较长的词。
有更复杂的方法，有限状态机和语言模型可以生成多个分段并应用概率排序。
于 2012-01-08T09:58:43.887 回答
0
如果您确定字典中有该短语的所有单词，则可以使用该算法：
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 左右。
于 2011-06-20T08:00:15.007 回答
0
我告诉过你，这似乎是一项不可能完成的任务。但是您可以查看这个相关的 SO question - 它可能会对您有所帮助。
于 2011-06-20T08:00:27.267 回答
0
好的，我会尝试一下。您的问题的完美（ish）数据结构（正如您所说的那样）由字典中的单词组成。最好将 trie 可视化为DFA，这是一个很好的状态机，您可以在其中从一个状态转到每个新角色的下一个状态。这在代码中很容易做到，Java(ish) 风格的类将是：
Class State
{
String matchedWord;
Map<char,State> mapChildren;
}
从这里开始，构建 trie 就很容易了。它就像一个有根的树结构，每个节点都有多个子节点。每个孩子都在一个字符转换上被访问。一种结构的使用HashMap减少了查找字符到下一个State映射的时间。或者，如果您只有 26 个字母表字符，afixed size array of 26也可以解决问题。
现在，假设所有这些都是有道理的，你有一个尝试，你的问题仍然没有完全解决。这是您开始做正则表达式引擎之类的事情的地方，沿着特里树走，跟踪与字典中的整个单词匹配的状态（这就是我matchedWord在结构中的 for State），使用一些回溯逻辑跳转到如果当前路径遇到死胡同，则为先前的匹配状态。我知道它的一般性，但考虑到 trie 结构，其余部分相当简单。
于 2011-06-23T00:52:24.500 回答