创建树形数据结构

问题描述 投票:0回答:2

我有一些数据:

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) стул по доступным ценам

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

c# algorithm nlp morphological-analysis
2个回答
1
投票

嗯,

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

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

后缀树

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


1
投票

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

然后继续写两个词的句子。您必须将它们中的每一个与每个单字父节点进行匹配,这将非常慢,因为您的比较函数很慢。不过,您可以进行两项优化:首先检查单词是否“完全”相同。您可以自己完成此操作,而且速度会很快。另一种是记住每对比较单词的比较函数的结果。你会浪费一些内存,但你会获得一些速度。 当节点匹配时,将句子添加到其中。当句子不匹配任何节点时,将其设为父节点。

对于长度逐渐增加的句子,您也可以执行相同的操作,只是您必须尝试匹配匹配节点的子节点,以找到添加句子的正确位置。

© www.soinside.com 2019 - 2024. All rights reserved.