分享好友 编程语言首页 频道列表

.NET下文本相似度算法余弦定理和SimHash浅析及应用实例分析

ASP.NET  2015-06-24 09:580

本文实例讲述了.NET下文本相似度算法余弦定理和SimHash浅析及应用。分享给大家供大家参考。具体分析如下:

余弦相似性

原理:首先我们先把两段文本分词,列出来所有单词,其次我们计算每个词语的词频,最后把词语转换为向量,这样我们就只需要计算两个向量的相似程度.
 
我们简单表述如下
 
文本1:我/爱/北京/天安门/ 经过分词求词频得出向量(伪向量)  [1,1,1,1]
 
文本2:我们/都爱/北京/天安门/ 经过分词求词频得出向量(伪向量)  [1,0,1,2]
 
我们可以把它们想象成空间中的两条线段,都是从原点([0, 0, ...])出发,指向不同的方向。两条线段之间形成一个夹角,如果夹角为0度,意味着方向相同、线段重合;如果夹角为90度,意味着形成直角,方向完全不相似;如果夹角为180度,意味着方向正好相反。因此,我们可以通过夹角的大小,来判断向量的相似程度。夹角越小,就代表越相似。
 
C#核心算法:

复制代码 代码如下:
    public class TFIDFMeasure
    {
        private string[] _docs;
        private string[][] _ngramDoc;
        private int _numDocs=0;
        private int _numTerms=0;
        private ArrayList _terms;
        private int[][] _termFreq;
        private float[][] _termWeight;
        private int[] _maxTermFreq;
        private int[] _docFreq;
 
        public class TermVector
        {       
            public static float ComputeCosineSimilarity(float[] vector1, float[] vector2)
            {
                if (vector1.Length != vector2.Length)               
                    throw new Exception("DIFER LENGTH");
               
 
                float denom=(VectorLength(vector1) * VectorLength(vector2));
                if (denom == 0F)               
                    return 0F;               
                else               
                    return (InnerProduct(vector1, vector2) / denom);
               
            }
 
            public static float InnerProduct(float[] vector1, float[] vector2)
            {
           
                if (vector1.Length != vector2.Length)
                    throw new Exception("DIFFER LENGTH ARE NOT ALLOWED");
               
           
                float result=0F;
                for (int i=0; i < vector1.Length; i++)               
                    result += vector1[i] * vector2[i];
               
                return result;
            }
       
            public static float VectorLength(float[] vector)
            {           
                float sum=0.0F;
                for (int i=0; i < vector.Length; i++)               
                    sum=sum + (vector[i] * vector[i]);
                       
                return (float)Math.Sqrt(sum);
            }
        }
 
        private IDictionary _wordsIndex=new Hashtable() ;
 
        public TFIDFMeasure(string[] documents)
        {
            _docs=documents;
            _numDocs=documents.Length ;
            MyInit();
        }
 
        private void GeneratNgramText()
        {
           
        }
 
        private ArrayList GenerateTerms(string[] docs)
        {
            ArrayList uniques=new ArrayList() ;
            _ngramDoc=new string[_numDocs][] ;
            for (int i=0; i < docs.Length ; i++)
            {
                Tokeniser tokenizer=new Tokeniser() ;
                string[] words=tokenizer.Partition(docs[i]);           
 
                for (int j=0; j < words.Length ; j++)
                    if (!uniques.Contains(words[j]) )               
                        uniques.Add(words[j]) ;
            }
            return uniques;
        }

        private static object AddElement(IDictionary collection, object key, object newValue)
        {
            object element=collection[key];
            collection[key]=newValue;
            return element;
        }
 
        private int GetTermIndex(string term)
        {
            object index=_wordsIndex[term];
            if (index == null) return -1;
            return (int) index;
        }
 
        private void MyInit()
        {
            _terms=GenerateTerms (_docs );
            _numTerms=_terms.Count ;
 
            _maxTermFreq=new int[_numDocs] ;
            _docFreq=new int[_numTerms] ;
            _termFreq =new int[_numTerms][] ;
            _termWeight=new float[_numTerms][] ;
 
            for(int i=0; i < _terms.Count ; i++)           
            {
                _termWeight[i]=new float[_numDocs] ;
                _termFreq[i]=new int[_numDocs] ;
 
                AddElement(_wordsIndex, _terms[i], i);           
            }
           
            GenerateTermFrequency ();
            GenerateTermWeight();           
        }
       
        private float Log(float num)
        {
            return (float) Math.Log(num) ;//log2
        }
 
        private void GenerateTermFrequency()
        {
            for(int i=0; i < _numDocs  ; i++)
            {                               
                string curDoc=_docs[i];
                IDictionary freq=GetWordFrequency(curDoc);
                IDictionaryEnumerator enums=freq.GetEnumerator() ;
                _maxTermFreq[i]=int.MinValue ;
                while (enums.MoveNext())
                {
                    string word=(string)enums.Key;
                    int wordFreq=(int)enums.Value ;
                    int termIndex=GetTermIndex(word);
 
                    _termFreq [termIndex][i]=wordFreq;
                    _docFreq[termIndex] ++;
 
                    if (wordFreq > _maxTermFreq[i]) _maxTermFreq[i]=wordFreq;                   
                }
            }
        }

        private void GenerateTermWeight()
        {           
            for(int i=0; i < _numTerms   ; i++)
            {
                for(int j=0; j < _numDocs ; j++)               
                    _termWeight[i][j]=ComputeTermWeight (i, j);
            }
        }
 
        private float GetTermFrequency(int term, int doc)
        {           
            int freq=_termFreq [term][doc];
            int maxfreq=_maxTermFreq[doc];           
           
            return ( (float) freq/(float)maxfreq );
        }
 
        private float GetInverseDocumentFrequency(int term)
        {
            int df=_docFreq[term];
            return Log((float) (_numDocs) / (float) df );
        }
 
        private float ComputeTermWeight(int term, int doc)
        {
            float tf=GetTermFrequency (term, doc);
            float idf=GetInverseDocumentFrequency(term);
            return tf * idf;
        }
       
        private  float[] GetTermVector(int doc)
        {
            float[] w=new float[_numTerms] ;
            for (int i=0; i < _numTerms; i++)
                w[i]=_termWeight[i][doc];
            return w;
        }
 
        public float GetSimilarity(int doc_i, int doc_j)
        {
            float[] vector1=GetTermVector (doc_i);
            float[] vector2=GetTermVector (doc_j);
            return TermVector.ComputeCosineSimilarity(vector1, vector2);
        }
       
        private IDictionary GetWordFrequency(string input)
        {
            string convertedInput=input.ToLower() ;
            Tokeniser tokenizer=new Tokeniser() ;
            String[] words=tokenizer.Partition(convertedInput);
            Array.Sort(words);
           
            String[] distinctWords=GetDistinctWords(words);
                       
            IDictionary result=new Hashtable();
            for (int i=0; i < distinctWords.Length; i++)
            {
                object tmp;
                tmp=CountWords(distinctWords[i], words);
                result[distinctWords[i]]=tmp;
            }
            return result;
        }               
               
        private string[] GetDistinctWords(String[] input)
        {               
            if (input == null)           
                return new string[0];           
            else
            {
                ArrayList list=new ArrayList() ;
               
                for (int i=0; i < input.Length; i++)
                    if (!list.Contains(input[i])) // N-GRAM SIMILARITY
                        list.Add(input[i]);
                return Tokeniser.ArrayListToArray(list) ;
            }
        }

        private int CountWords(string word, string[] words)
        {
            int itemIdx=Array.BinarySearch(words, word);
           
            if (itemIdx > 0)           
                while (itemIdx > 0 && words[itemIdx].Equals(word))
                    itemIdx--;               
            int count=0;
            while (itemIdx < words.Length && itemIdx >= 0)
            {
                if (words[itemIdx].Equals(word)) count++;
                itemIdx++;
                if (itemIdx < words.Length)               
                    if (!words[itemIdx].Equals(word)) break;
            }
            return count;
        }               
}


 
缺点:
 
由于有可能一个文章的特征向量词特别多导致整个向量维度很高,使得计算的代价太大不适合大数据量的计算。
 
SimHash原理:
 
算法的主要思想是降维,将高维的特征向量映射成一个f-bit的指纹(fingerprint),通过比较两篇文章的f-bit指纹的Hamming Distance来确定文章是否重复或者高度近似。由于每篇文章我们都可以事先计算好Hamming Distance来保存,到时候直接通过Hamming Distance来计算,所以速度非常快适合大数据计算。
 
Google就是基于此算法实现网页文件查重的。我们假设有以下三段文本:
 
1,the cat sat on the mat
 
2,the cat sat on a mat
 
3,we all scream for ice cream
 
如何实现这种hash算法呢?以上述三个文本为例,整个过程可以分为以下六步:
1、选择simhash的位数,请综合考虑存储成本以及数据集的大小,比如说32位
2、将simhash的各位初始化为0
3、提取原始文本中的特征,一般采用各种分词的方式。比如对于"the cat sat on the mat",采用两两分词的方式得到如下结果:{"th", "he", "e ", " c", "ca", "at", "t ", " s", "sa", " o", "on", "n ", " t", " m", "ma"}
4、使用传统的32位hash函数计算各个word的hashcode,比如:"th".hash = -502157718
,"he".hash = -369049682,……
5、对各word的hashcode的每一位,如果该位为1,则simhash相应位的值加1;否则减1
6、对最后得到的32位的simhash,如果该位大于1,则设为1;否则设为0

希望本文所述对大家的.net程序设计有所帮助。

查看更多关于【ASP.NET】的文章

展开全文
相关推荐
反对 0
举报 0
评论 0
图文资讯
热门推荐
优选好物
更多热点专题
更多推荐文章
Windows API Reference for C#, VB.NET
不错的.net 下用API的参考站点地址在:http://www.webtropy.com/articles/Win32-API-DllImport-art9.asp 下面摘抄分类,便于大家直接就拿来用: File, Memory, Process, Threading, Time, Console, and Comm control(kernel32.dll) _hread_hwrite_lclose_lcr

0评论2023-03-16877

一个基于API的VB.net串口通讯类 vbnet串口通信如何编写
VB.net的串口通讯支持总是让人觉得有所不足,在使用VB6的MsComm32.ocx时,很多人都会在VB.net的开发中觉得很困扰。    这里讲述的VB.net串口通讯类使用native代码,并且它是通API调用实现的,你会发现VB.net的串口通讯就是这么简单。    在说明如何使

0评论2023-02-12420

[VB][ASP.NET]FileUpload控件「批次上传 / 多档案同时上传」的范例
FileUpload控件「批次上传 / 多档案同时上传」的范例 (VB语法) http://www.dotblogs.com.tw/mis2000lab/archive/2008/05/14/3986.aspx    FileUpload控件真的简单好用,不使用它来作批次上传,却要改用别的方法,实在不聪明。要用就一次用到底,公开File

0评论2023-02-10976

VB.NET调用IE,并且等待
            Dim p As New Process            '获得URL            aURL = GetURL()            '获得IE路径            p.StartInfo.FileName = System.Environment.GetFolderPath( _ 

0评论2023-02-09939

VB.NET withevent 自定义事件处理
Module Module1    Private WithEvents aemp As part2    Sub Main()        Dim chen As New part2("chen lili", 20000)        aemp = chen        Console.WriteLine(chen.Name" prevouis salary is "chen.Salary)      

0评论2023-02-09571

ASP.NET操作Cookies的问题(Bug or Not)
以下存和取都是在不同的页面中,如果是在同一个页面也没必要用cookies了。 Test1: 给Cookies赋值: const string AAA="aaa"; Response.Cookies[AAA].Value = "111;222;333"; 取值: string value = Request.Cookies[AAA].Value; // value为111 Test2: 给Cooki

0评论2023-02-09888

Asp.Net Core 自定义验证属性
  很多时候,在模型上的验证需要自己定义一些特定于我们需求的验证属性。所以这一篇我们就来介绍一下怎么自定义验证属性。  我们来实现一个验证邮箱域名的自定义验证属性,当然,最重要的是需要定义一个继承自ValidationAttribute的类,然后在实现其IsVal

0评论2023-02-09525

Asp.Net 之 枚举类型的下拉列表绑定
有这样一个学科枚举类型:/// 学科 /// /summary public enum Subject {None = 0,[Description("语文")]Chinese = 1,[Description("数学")]Mathematics = 2,[Description("英语")]English = 3,[Description("政治")]Politics = 4,[Description("物理&qu

0评论2023-02-09819

[ASP.NET笔记] 1.Web基础知识
     1:http协议:     2:web服务器:     3:静态网页的概念     4:动态网页的概念       http协议:http(hypertext transfer protocol) 即超文本传输协议,这个协议是在internet上进行信息传送的协议任何网页之间要相互沟通,必须要尊循

0评论2023-02-09663

ASP.NET邮件发送 .net 发送邮件
  今天做了个ASP.NET做发送邮件功能,发现QQ邮箱好奇怪,当你用QQ邮箱做服务器的时候什么邮件都发送不出去(QQ邮箱除外)。而且爆出这样的错误:"邮箱不可用。 服务器响应为: Error: content rejected.http://mail.qq.com/zh_CN/help/content/rejectedmail.ht

0评论2023-02-09455

由ASP.NET Core根据路径下载文件异常引发的探究
前言    最近在开发新的项目,使用的是ASP.NET Core6.0版本的框架。由于项目中存在文件下载功能,没有使用类似MinIO或OSS之类的分布式文件系统,而是下载本地文件,也就是根据本地文件路径进行下载。这其中遇到了一个问题,是关于如何提供文件路径的,通

0评论2023-02-09562

ASP.NET 后台接收前台POST过来的json数据方法
 ASP.NET前后台交互之JSON数据 https://www.cnblogs.com/ensleep/p/3319756.html

0评论2023-02-09501

Asp.Net 常用工具类之加密——对称加密DES算法(2)
     又到周末,下午博客园看了两篇文章,关于老跳和老赵的程序员生涯,不禁感叹漫漫程序路,何去何从兮!  转眼毕业的第三个年头,去过苏州,跑过上海,从一开始的凌云壮志,去年背起行囊默默回到了长沙准备买房,也想有个家(毕竟年级不小了),有盼

0评论2023-02-09995

更多推荐