索引句子的最佳算法

想象一下，我有一種情況需要索引句子。讓我稍微解釋一下。索引句子的最佳算法

例如，我有這些句子：

美麗的星空。
美麗的天空夢想。
美麗的夢想。

至於我能想象的指數應該是這個樣子：

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

索引句子的最佳算法

回答

相關問題