尋找相似的單詞或短語從兩個文本

我知道如何比較兩個文本，並獲得所有出現在這兩個單詞。但是我怎麼能匹配表達式/短語？尋找相似的單詞或短語從兩個文本

例如： 1.「這是電腦製造商蘋果」 2.「蘋果是一家總部位於加州大電腦製造商」

現在:)

蘋果是明顯存在都。
計算機和製造商都存在於兩者。我可以在這一點上檢查它們是否是一組詞（另一個是一個）。

但對於處理的速度，是不是有一種方法來匹配「計算機制造商」，而不是每一個，然後檢查是否存在的基團。

請記住，給出的例子很簡單，只是爲了舉例說明，實際上可能會出現更復雜的句子/文本。

來源

2011-09-08 Andrew

您可以解析這兩個字符串並分割空白以獲取令牌數組A1和A2。然後，簡單地檢查A1中每個連續的子序列是否與A2中的匹配。這對我來說看起來像O（n^4），這比獲得所有單個匹配和尋找組合不是多項式更好。

1. the cat is on the roof 
    2. a man is on the stage 

    A1 = [the, cat, is, on, the, roof] 
    A2 = [a, man, is, on, the, stage] 

    [the]: no match 
    [cat]: no match 
    [is]: match 
    [is, on]: match 
    [is, on, the]: match 
    [is, on, the, roof]: no match 
    [on]: match 
    [on, the]: match 
    [on, the, roof]: no match 
    [the]: match 
    [the, roof]: no match 
    [roof]: no match 
    -end-

遞歸似乎是一種優雅的方式來實現這樣的事情。如果你需要更有效率的東西，我相信有一個更明智的方法來做到這一點。

來源

2011-09-08 18:27:22 Patrick87

希望Google不會使用O（n^4）algorythm來檢查網站中的內容修改。 – Alfwed

沒錯，但有一些意見......這很容易理解，比OP的建議好得多，它的平均情況表現可能比O（n^4）好得多，可能更接近O（n^2）。 – Patrick87

編輯：這聽起來像你可能正在尋找解決方案the longest common substring problem，或更一般的the longest common subsequence problem。如果是這樣的話，那麼你基本上需要對「差異」實用程序進行修改，而實施的細節很大程度上取決於你的要求的細節。

來源

2011-09-08 18:19:32 Peter

如果他想要所有常見的字符串，這似乎不是正確的方式去...也許我失去了一些東西。也許LCS的規範解決方案訪問所有候選人，因此可以列舉它們？ – Patrick87

-1用於回答有問題的問題。如果這是你正在尋找的東西，你應該留下它作爲評論。 – barfoon

@barfoon：語義詭辯，國際海事組織。但我不是專家，所以如果這是我們在這裏的方式，那很好。 – Peter

尋找相似的單詞或短語從兩個文本

回答

相關問題