从随机字符串中分离真实字词

我存储了在网站上的所有搜索中使用的关键字列表，并且我在关键字字段中收到了大量随机字符串。下面是我得到回数据的样本：从随机字符串中分离真实字词

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

从随机字符串中分离真实字词

回答

相关问题