3

我有一些数据：

A
AXNHJNEHWXNOECMEJK
DNFJNXYEEQWhsdbchjsxs
XMJQWsdsEOJdfsKMDJE

……

每行都是数组，每个字母都是对象。我有比较器功能，可以说字母 A 与字母 a 等价（实际上它不是字母。它是俄语单词，比较器功能使用形态学让我知道单词相等，例如 матрешка==матрешки==матрешкины 和数组俄语句子。例如：“Мама мыла раму”）。我想创建如下所示的树数据结构：

1) A
2.1) BA
2.2) DHBAFH
3.1) BEDMEWA
etc...

否则子节点必须包含来自父节点的字母。如果您知道如何使用 google adwords，我想您可以理解我。我的问题是如何快速做到这一点。我需要用数千个数组创建树。比较功能工作得非常慢（它使用大字典），这就是为什么速度是真正的问题。

一些简单的数据（对不起俄语）：

这是一组句子

сайты        
сайты недорого
сайты дешево
сайты дешево и быстро
красивый сайт по доступным ценам 
хочу купить хороший стул 
стул по доступным ценам

我们必须创建以下树数据结构

1) сайты
1->2.1) сайты недорого
1->2.2) сайты дешево
1->2.3) красивый сайт по доступным ценам 
1->2.2->3) сайты дешево и быстро

其他父节点：

1) хочу купить хороший стул 
1) стул по доступным ценам

子节点必须包含比父节点更多的单词。

4

2 回答 2

1

出色地，

似乎此链接可能对您的问题有所帮助

使用后缀树进行快速字符串搜索：http: //marknelson.us/1996/08/01/suffix-trees/

和

后缀树

http://en.wikipedia.org/wiki/Suffix_tree

于 2011-05-21T15:30:19.573 回答
1

从只有一个单词的句子开始。它们都将成为父节点，所以这很简单。

然后继续两个词的句子。您必须将它们中的每一个与每个单字父节点匹配，这将非常慢，因为您的比较功能很慢。不过，您可以进行两种优化：首先检查单词是否完全相同。你可以自己做，而且速度很快。另一种是记住每对比较词的比较函数的结果。你会浪费一些内存，但你会获得一些速度。

当一个节点匹配时，将句子添加到它。当句子不匹配任何节点时，使其成为父节点。

对于长度逐渐增加的句子，您也可以这样做，除了您必须尝试匹配匹配节点的子节点，以找到添加句子的正确位置。

于 2011-05-21T21:35:16.133 回答