索引句子的最佳算法

想象一下，我有一种情况需要索引句子。让我稍微解释一下。索引句子的最佳算法

例如，我有这些句子：

美丽的星空。
美丽的天空梦想。
美丽的梦想。

至于我能想象的指数应该是这个样子：

alt text http://img7.imageshack.us/img7/4029/indexarb.png

而且我想任何的这些话做搜索。

例如，如果我通过“the”搜索它应该显示给我连接到“美丽”。如果我通过“美丽”进行搜索，它应该给我连接（上一个）“The”，（下一个）“天空”和“梦想”。如果我搜索“天空”，它应该（先前）连接到“美丽”等...

任何想法？也许你知道这种问题已经存在的算法？

来源

2009-04-08 Lukas Šalkauskas

使用关联数组可以让您快速解析Perl中的句子。它比你预期的要快得多，并且可以像结构树那样有效地排出，以供后续的高级语言使用。你想要一个算法。 – ojblass 2009-04-08 06:24:03

@LukasŠalkauskas，你为什么要删除这个问题？这很棒。图表中只有一个错字。 – 2009-04-09 06:50:51

这个现在应该让你关闭，在C＃：

class Program 
{ 
    public class Node 
    { 
     private string _term; 
     private Dictionary<string, KeyValuePair<Node, Node>> _related = new Dictionary<string, KeyValuePair<Node, Node>>(); 

     public Node(string term) 
     { 
      _term = term; 
     } 

     public void Add(string phrase, Node previous, string [] phraseRemainder, Dictionary<string,Node> existing) 
     { 
      Node next= null; 
      if (phraseRemainder.Length > 0) 
      { 
       if (!existing.TryGetValue(phraseRemainder[0], out next)) 
       { 
        existing[phraseRemainder[0]] = next = new Node(phraseRemainder[0]); 
       } 
       next.Add(phrase, this, phraseRemainder.Skip(1).ToArray(), existing); 
      } 
      _related.Add(phrase, new KeyValuePair<Node, Node>(previous, next)); 

     } 
    } 


    static void Main(string[] args) 
    { 
     string [] sentences = 
      new string [] { 
       "The beautiful sky", 
       "Beautiful sky dream", 
       "beautiful dream" 
      }; 

     Dictionary<string, Node> parsedSentences = new Dictionary<string,Node>(); 

     foreach(string sentence in sentences) 
     { 
      string [] words = sentence.ToLowerInvariant().Split(' '); 
      Node startNode; 
      if (!parsedSentences.TryGetValue(words[0],out startNode)) 
      { 
       parsedSentences[words[0]] = startNode = new Node(words[0]); 
      } 
      if (words.Length > 1) 
       startNode.Add(sentence,null,words.Skip(1).ToArray(),parsedSentences); 
     } 
    } 
}

我把假设你想保留的实际初始短语的自由。最后，你会在短语中列出单词列表，并在每个短语列表中使用该单词的短语列表，以及每个短语中下一个和前一个单词的引用。

来源

2009-04-08 07:12:33

-4

树搜索算法（如BST，ECT）

来源

2009-04-08 06:16:05 Dhana

我不会称之为二进制... – Paulius 2009-04-08 06:18:29

使用的associative array将允许您快速分析句子在Perl。它比你预期的要快得多，并且可以像结构树那样有效地排出，以供后续的高级语言使用。

来源

2009-04-08 06:21:19 ojblass

你可以尝试挖掘Markov chains，从句子的话形成。此外，您还需要双向链（即查找下一个和前一个单词），即存储紧随给定或之前出现的可能词。

当然，马尔可夫链是一个生成内容的随机过程，然而类似的方法可能被用来存储你需要的信息。

来源

2009-04-08 06:21:55 dragonfly

这看起来像它可以被存储在一个非常简单的数据库具有以下表：

Words: 
    Id  integer primary-key 
    Word varchar(20) 
Following: 
    WordId1 integer foreign-key Words(Id) indexed 
    WordId2 integer foreign-key Words(Id) indexed

然后，当你分析一个句子，只需插入尚不存在的那些，具体如下：

The beautiful sky. 
    Words (1,'the') 
    Words (2, 'beautiful') 
    Words (3,, 'sky') 
    Following (1, 2) 
    Following (2, 3) 
Beautiful sky dream. 
    Words (4, 'dream') 
    Following (3, 4) 
Beautiful dream. 
    Following (2, 4)

然后你就可以查询到你的心内容是什么字后面或前面等字样。

来源

2009-04-08 06:25:17 paxdiablo

简答

与以前/前向链路的两个向量创建一个结构。然后将单词结构存储在散列表中，并将其作为单词本身。

长的答案

这是一种语言分析问题不容易解决，除非你不介意的胡言乱语。

我去公园篮球场。
你会停放汽车。

您链接算法将创建这样的句子：

我坐车去了公园。
你会停放篮球场吗？

我不太确定这个SEO的应用，但我不会欢迎另一个垃圾邮件网站占据搜索结果。

来源

2009-04-08 06:51:58 Unknown

我想你会想要某种Inverted index结构。您将有一个Hashmap，其中的关键词指向表格(sentence_id, position)。然后你会将你的句子存储为数组或链表。您的示例如下所示：

sentence[0] = ['the','beautiful', 'sky']; 
sentence[1] = ['beautiful','sky', 'dream']; 
sentence[2] = ['beautiful', 'dream']; 

inverted_index = 
{ 
'the': {(0,0)}, 
'beautiful': {(0,1), (1,0), (2,0)}, 
'sky' : {(0,2),(1,1)}, 
'dream':{(1,2), (2,1)} 
};

使用此结构可以在固定时间内对单词进行查找。识别出你想要的单词后，在给定的句子中查找前一个单词和后一个单词也可以在不变的时间内完成。

希望这会有所帮助。

来源

2009-04-08 07:18:37

索引句子的最佳算法

回答

相关问题