從隨機字符串中分離真實字詞

我存儲了在網站上的所有搜索中使用的關鍵字列表，並且我在關鍵字字段中收到了大量隨機字符串。下面是我得到回數據的樣本：從隨機字符串中分離真實字詞

fRNPRXiPtjDrfTDKH 
boom 
Mule deer 
gVXOFEzRWi 
cbFXZcCoSiKcmrvs 
Owner Financed ,owner Financed

我試圖找到在SQL或ColdFusion的方式來弄清楚，如果事情有有效的英文單詞，或者如果它是一個隨機的字符集。我試着做一些挖掘n-gram分析的工作，但似乎無法提出任何可以直接在我的服務器上運行的有用解決方案。

來源

2012-11-26 Dan Short

UPDATE：現在的代碼是的jsfiddle：http://jsfiddle.net/ybanrab/s6Bs5/1/它可能是有趣的測試中的數據複製和粘貼的新聞副本頁面並粘貼

我建議要分析單個字符的概率跟着彼此。以下是我編寫的JavaScript示例，但它應該很容易轉換爲T-SQL或ColdFusion。

這個想法是，你喂好的短語（語料庫）和分析其他字母后面的字母頻率。如果你給它「這個瘦」，你會得到這樣的事情：

{ 
t:{h:3}, 
h:{i:2,e:1}, 
i:{s:1,n:1}, 
s:{}, 
n:{} 
}

您可以通過從您要分析的數據欽點已知良好的投入飼養獲得最準確的，但你可能通過簡單的英語餵食也能獲得良好的效果。在下面的例子中，我正在計算這個，但是一旦你滿意，你顯然可以存儲它。

然後您運行示例字符串反對概率給它一個分數。這個版本忽略大小寫，單詞起始字母，長度等，但如果你願意的話，你也可以使用它們。然後，您只需要決定一個閾值分數並像那樣過濾。

我很確定這種分析有一個名字，但我的google-fu今天很弱。您可以將下面的代碼粘貼到腳本塊中，以瞭解它的工作原理（或不工作）。

var corpus=["boom","Mule Deer", "Owner Financed ,owner Financed", "This is a valid String","The quick brown fox jumped over the lazy dog"]; 

var probs={}; 
var previous=undefined; 

//Compute the probability of one letter following another 
corpus.forEach(function(phrase){ 
    phrase.split(" ").forEach(function(word){ 
     word.toLowerCase().split("").forEach(function(chr){ 
      //set up an entry in the probabilities table 
      if(!probs[chr]){ 
       probs[chr]={}; 
      } 
      //If this isn't the first letter in the word, record this letter as following the previous one 
      if(previous){ 
       if(!probs[previous][chr]){ 
        probs[previous][chr]=0; 
       } 
       probs[previous][chr]++; 
      } 
      //keep track of the previous character 
      previous=chr; 

     }); 
     //reset previous as we're moving onto a different word 
     previous=undefined; 
    }) 
}); 


function calculateProbability(suspect){ 
    var score=0; 
    var previous=undefined; 
    suspect.toLowerCase().split("").forEach(function(chr){ 
     if(previous && probs[previous] && probs[previous][chr]){ 
      //Add the score if there is one, otherwise zero 
      score+=probs[previous][chr]; 
     } 
     previous=chr; 
    }); 
    return score/suspect.length; 
} 

console.log(calculateProbability("boom")); 
console.log(calculateProbability("Mood")); 
console.log(calculateProbability("Broom")); 
console.log(calculateProbability("sajkdkas dak"));

來源

2012-11-26 15:51:10 barnyr

這個解決方案絕對給我一些想法。我會做一些實驗，如果這樣做結束了工作，我一定會將其標記爲公認的答案。 –

謝謝，我已經更新了這裏的小提琴：http://jsfiddle.net/ybanrab/39E5c/這一個試圖糾正單詞的數量，以提供更一致的分數。我認爲這似乎足夠合理。感謝您發佈這個問題，這是一個非常有趣的攻擊問題 – barnyr

您正在進行人物n-gram建模，但有一個例外：您的calculateProbability方法應該乘以概率，而不是將它們相加。這樣做可能會下溢，所以您可以對日誌進行求和，然後按字長對其進行歸一化。與基於單詞的分析相反，這將允許您查找未被視爲單詞的類似單詞的字符串，代價是被僅在馬爾可夫視界以外非字的字符串所欺騙。 –

有一些非字典詞可以是有效的搜索（例如，gethostbyname是對SO的有效且有意義的搜索，但不是詞典詞）。另一方面，詞典中的詞絕對與您的網站無關。

您可以簡單地檢查搜索查詢是否生成非空結果，而不是試圖猜測什麼是單詞，什麼不是。那些空洞的結果必須是完整的話題或亂碼。

來源

2012-11-26 15:07:59

可能，但我們希望保持非零結果，以便我們知道誰在搜索什麼。只是因爲我沒有人想要的東西，並不意味着它不是一個有效的搜索:)。而這個特定的網站不會有任何無意義的話，因爲它的重點非常狹窄。 –

檢查是否英文單詞是唯一可靠的方法是在字典中查找它。你需要一個可搜索的英文字典，以某種形式開始。 –

這聽起來像你正在尋找一個

Bayesian Filter

來源

2012-11-26 15:53:12

做的最好的事情就是檢查你的話對頻率列表：詞典不能起作用，因爲它們不包含語法變形，專有名詞，複合詞以及其他有效的東西。

天真檢查n-gram數據的問題是低頻詞中有很多噪音。在絕大多數情況下應該給你正確答案的最簡單的事情是從頂部50,000或100,000字的適當大的地方（Google n-gram，維基百科等）截斷頻率計數單詞列表。根據需要調整閾值以獲得您要查找的結果，但是您可以檢查是否有任何/所有查詢條件出現在此列表中。

如果你想知道查詢是否是語法的，或者作爲一個單元而不是它的組成部分是合理的，那當然是另外一個問題了。

來源

2012-11-26 16:26:06

從隨機字符串中分離真實字詞

回答

相關問題