解析短語到不同的單詞配對

Question

我想弄清楚什麼是最好的方法來解析傳遞給我的單詞短語，並基於這些短語建立不同的分組。

示例XML：

<root> 
    <keyword value=""My First Phrase""/> 
    <keyword value=""My First Phrase Again""/> 
    <keyword value=""My First Phrase Again and Again""/> 
</root> 

所以我會提取這些列的XML的：

My First Phrase 
My First Phrase Again 
My First Phrase Again and Again 

我會再像從原來建立這些新的短語：

My First Phrase 
My First 
First Phrase 
My 
First 
Phrase 

My First Phrase Again 
My First Phrase 
First Phrase Again 
My First 
First Phrase 
Phrase Again 
My 
First 
Phrase 
Again 

這會讓我分解這些短語，並從這些單詞中建立一種排序。我已經建立了一些列表並迭代了它們，但它並不按我期望的方式工作。

所以對於排名我的意思是這樣的：

My First Phrase Again Rank: 1 (Exact Match) 
My First Phrase   Rank: 2 
First Phrase Again  Rank: 2 
My First     Rank: 3 
First Phrase    Rank: 3 
Phrase Again    Rank: 3 
My      Rank: 4 
First     Rank: 4 
Phrase     Rank: 4 
Again     Rank: 4 

不知道什麼是最好的辦法是分析這些數據。

感謝，

小號

Answer 1

如果我理解正確的話你的 '等級' 的定義，你可以用這樣的事情解決這個問題：

public class PhraseRanking : IEnumerable<KeyValuePair<string, int>> 
{ 
    private readonly Dictionary<string, int> _ranking; 

    public PhraseRanking() 
    { 
     _ranking = new Dictionary<string, int>(); 
    } 

    public PhraseRanking(string phrase) 
     : this() 
    { 
     var words = phrase.Split(new[] { ' ' }, StringSplitOptions.RemoveEmptyEntries); 
     var sb = new StringBuilder(phrase.Length); 
     for(int i = words.Length; i > 0; --i) 
     { 
      int rank = words.Length - i + 1; 
      int lastFirstWordIndex = words.Length - i; 
      for(int j = 0; j <= lastFirstWordIndex; ++j) 
      { 
       sb.Clear(); 
       int lastWordIndex = j + i - 1; 
       for(int k = j; k <= lastWordIndex; ++k) 
       { 
        sb.Append(words[k]); 
        if(k != lastWordIndex) sb.Append(' '); 
       } 
       _ranking[sb.ToString()] = rank; 
      } 
     } 
    } 

    public int this[string phrase] 
    { 
     get { return _ranking[phrase]; } 
    } 

    public int Count 
    { 
     get { return _ranking.Count; } 
    } 

    public IEnumerator<KeyValuePair<string, int>> GetEnumerator() 
    { 
     return _ranking.GetEnumerator(); 
    } 

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() 
    { 
     return _ranking.GetEnumerator(); 
    } 
} 

用法：

var ranking = new PhraseRanking("My First Phrase Again"); 
var sb = new StringBuilder(); 
foreach(var rank in ranking) 
{ 
    sb.AppendLine(rank.Value.ToString() + ": " + rank.Key); 
} 
MessageBox.Show(sb.ToString()); 

輸出：

1: My First Phrase Again 
2: My First Phrase 
2: First Phrase Again 
3: My First 
3: First Phrase 
3: Phrase Again 
4: My 
4: First 
4: Phrase 
4: Again 

Answer 2

這聽起來像你正在尋找發展grammar。您的排名看起來與parse tree中的令牌深度相同。您的終端符號將是任何單詞，您的開始符號將是您的root元素中列出的句子。

例如：

S -> X Y 
X -> M F 
Y -> P A 
M -> "My" 
F -> "First" 
P -> "Phrase" 
A -> "Again" 

在這種情況下，的「我的第一句話再一次」深度將0解析樹，「我的第一個」和「詞組再」的深度將是1 ，並且「我的」，「第一」，「短語」和「再次」的深度將是2.

我會開始尋找文法分析器。有很多這些可用，因爲它們用於編寫編譯器。或者你可以嘗試寫你自己的。上下文無關語法實現相當簡單;你真正需要的是一個堆棧和一種解釋和操作你的語法規則的方法。有很多關於這方面的文獻，因爲它是一個計算機科學領域的研究熱點。

Answer 3

你需要一個後綴數組，而不是按字符分隔，用「」標記分隔。 http://en.wikipedia.org/wiki/Suffix_array

在Programming Pearls中有很好的描述。