lsh 用于近似查詢，聚類分類，壓縮等領域。
漢明距離
漢明距離是以理查德·衛斯裡·漢明的名字命名的。在資訊論中，兩個等長字元串之間的漢明距離是兩個字元串對應位置的不同字元的個數。換句話說，它就是将一個字元串變換成另外一個字元串所需要替換的字元個數。例如：1011101 與 1001001 之間的漢明距離是 2。2143896 與 2233796 之間的漢明距離是 3。"toned" 與 "roses" 之間的漢明距離是 3。
漢明重量
漢明重量是字元串相對于同樣長度的零字元串的漢明距離，也就是說，它是字元串中非零的元素個數：對于二進制字元串來說，就是 1 的個數，是以 11101 的漢明重量是 4。
lsh(location sensitive hash),即位置敏感哈希函數。與一般哈希函數不同的是位置敏感性，也就是散列前的相似點經過哈希之後，也能夠在一定程度上相似，并且具有一定的機率保證。
對于任意q,p屬于s，若從集合s到u的函數族h={h1,h2...hn}對距離函數d(,)，如歐式距離、曼哈頓距離等等，滿足條件：
則稱d(,)是位置敏感的。
如下圖，空間上的點經位置敏感哈希函數散列之後，對于q，其rnn有可能散列到同一個桶（如第一個桶）,即散列到第一個桶的機率較大，會大于某一個機率門檻值p1;而其(1+emxilong)rnn之外的對象則不太可能散列到第一個桶，即散列到第一個桶的機率很小，會小于某個門檻值p2.
◆高維下近似查詢
相似性檢索在各種領域特别是在視訊、音頻、圖像、文本等含有豐富特征資訊領域中的應用變得越來越重要。豐富的特征資訊一般用高維向量表示，由此相似性檢索一般通過k近鄰或近似近鄰查詢來實作。一個理想的相似性檢索一般需要滿足以下四個條件：
1. 高準确性。即傳回的結果和線性查找的結果接近。
2. 空間複雜度低。即占用記憶體空間少。理想狀态下，空間複雜度随資料集呈線性增長，但不會遠大于資料集的大小。
3. 時間複雜度低。檢索的時間複雜度最好為o（1）或o（logn)。
4. 支援高次元。能夠較靈活地支援高維資料的檢索。
傳統主要方法是基于空間劃分的算法——tree類似算法，如r-tree，kd-tree，sr-tree。這種算法傳回的結果是精确的，但是這種算法在高維資料集上的時間效率并不高。實驗[1]指出次元高于10之後，基于空間劃分的算法時間複雜度反而不如線性查找。lsh方法能夠在保證一定程度上的準确性的前提下，時間和空間複雜度得到降低，并且能夠很好地支援高維資料的檢索。
◆分類和聚類
根據lsh的特性，即可将相近（相似）的對象散列到同一個桶之中，則可以對圖像、音視訊、文本等豐富的高維資料進行分類或聚類。
◆資料壓縮。如廣泛地應用于信号處理及資料壓縮等領域的vector quantization量子化技術。
總而言之，哪兒需要近似knn查詢，哪兒都能用上lsh.
[1] weber r, schek h, blott s. a quantitative analysis and performance study for similarity search methods in high dimensional spaces proc.of the 24th intl.conf.on very large data bases (vldb).1998:194-205
原文連結http://www.cnblogs.com/hxsyl/p/4518506.html
馬克·吐溫曾經說過，所謂經典小說，就是指很多人希望讀過，但很少人真正花時間去讀的小說。這種說法同樣适用于“經典”的計算機書籍。
最近一直在看lsh，不過由于matlab基礎比較差，一直沒搞懂。最近看的論文裡幾乎都是用simhash來實作lsh，進而進行ann。
有空看看基于滑動視窗的論文相似性檢測。
如何用matlab畫出一個數列（函數）的收斂過程（菱形收斂、圓形收斂）？
學完分布式了，我打算自己學wordpress，建立自己的獨立部落格，放在雲平台或者伺服器空間，然後學着分析流量和負載均衡這一類，這也算是資料挖掘了吧。
位運算隻适合整數哦。。。因為浮點的存儲方案決定不能位運算，如果非要位運算，就需要float.floattointbits，運算完，再通過float.intbitstofloat轉化回去。(java預設的float,double的hashcode其實就是對應的floattointbits的int值)
c++用fabs函數，java中用double.doubletolongbits函數，然後直接比較大小，内部原理不做探讨。
java中substring方法可以分解字元串，傳回的是原字元串的一個子字元串。如果要講一個字元串分解為一個一個的單詞或者标記，stringtokenizer可以幫你。
stringtokenizer确實更快些，至于為什麼jdk裡不推薦使用了，還要再研究（現在是split結合正規表達式）。
測試方法：用stringbuilder的append方法，構造100w字元串，然後分别分别測試并算時間就ok了。
final可以不再定義時候初始化，好像可以再構造方法裡初始化。
1、分詞，把需要判斷文本分詞形成這個文章的特征單詞。最後形成去掉噪音詞的單詞序列并為每個詞加上權重，我們假設權重分為5個級别（1~5）。比如：“ 美國“51區”雇員稱内部有9架飛碟，曾看見灰色外星人 ” ==> 分詞後為 “ 美國（4） 51區（5） 雇員（3） 稱（1） 内部（2） 有（1） 9架（3） 飛碟（5） 曾（1） 看見（3） 灰色（4） 外星人（5）”，括号裡是代表單詞在整個句子裡重要程度，數字越大越重要。
2、hash，通過hash算法把每個詞變成hash值，比如“美國”通過hash算法計算為 100101,“51區”通過hash算法計算為 101011。這樣我們的字元串就變成了一串串數字，還記得文章開頭說過的嗎，要把文章變為數字計算才能提高相似度計算性能，現在是降維過程進行時。
3、權重，通過 2步驟的hash生成結果，需要按照單詞的權重形成權重數字串，比如“美國”的hash值為“100101”，通過權重計算為“4 -4 -4 4 -4 4”；“51區”的hash值為“101011”，通過權重計算為 “ 5 -5 5 -5 5 5”。
4、合并，把上面各個單詞算出來的序列值累加，變成隻有一個序列串。比如 “美國”的 “4 -4 -4 4 -4 4”，“51區”的 “ 5 -5 5 -5 5 5”， 把每一位進行累加， “4+5 -4+-5 -4+5 4+-5 -4+5 4+5” ==》 “9 -9 1 -1 1 9”。這裡作為示例隻算了兩個單詞的，真實計算需要把所有單詞的序列串累加。
5、降維，把4步算出來的 “9 -9 1 -1 1 9” 變成 0 1 串，形成我們最終的simhash簽名。 如果每一位大于0 記為 1，小于0 記為 0。最後算出結果為：“1 0 1 0 1 1”。
這個算法的幾何意義非常明了。它首先将每一個特征映射為f維空間的一個向量，這個映射規則具體是怎樣并不重要，隻要對很多不同的特征來說，它們對所對應的向量是均勻随機分布的，并且對相同的特征來說對應的向量是唯一的就行。比如一個特征的4位hash簽名的二進制表示為1010，那麼這個特征對應的 4維向量就是(1, -1, 1, -1)t，即hash簽名的某一位為1，映射到的向量的對應位就為1，否則為-1。然後，将一個文檔中所包含的各個特征對應的向量權重求和，權重的系數等于該特征的權重。得到的和向量即表征了這個文檔，我們可以用向量之間的夾角來衡量對應文檔之間的相似度。最後，為了得到一個f位的簽名，需要進一步将其壓縮，如果和向量的某一維大于0，則最終簽名的對應位為1，否則為0。這樣的壓縮相當于隻留下了和向量所在的象限這個資訊，而64位的簽名可以表示多達264個象限，是以隻儲存所在象限的資訊也足夠表征一個文檔了。
明确了算法了幾何意義，使這個算法直覺上看來是合理的。但是，為何最終得到的簽名相近的程度，可以衡量原始文檔的相似程度呢？這需要一個清晰的思路和證明。在simhash的發明人charikar的論文中并沒有給出具體的simhash算法和證明，以下列出我自己得出的證明思路。
simhash是由随機超平面hash算法演變而來的，随機超平面hash算法非常簡單，對于一個n維向量v，要得到一個f位的簽名(f<<n)，算法如下：
1，随機産生f個n維的向量r1,…rf；
2，對每一個向量ri，如果v與ri的點積大于0，則最終簽名的第i位為1，否則為0.
這個算法相當于随機産生了f個n維超平面，每個超平面将向量v所在的空間一分為二，v在這個超平面上方則得到一個1，否則得到一個0，然後将得到的 f個0或1組合起來成為一個f維的簽名。如果兩個向量u, v的夾角為θ，則一個随機超平面将它們分開的機率為θ/π，是以u, v的簽名的對應位不同的機率等于θ/π。是以，我們可以用兩個向量的簽名的不同的對應位的數量，即漢明距離，來衡量這兩個向量的差異程度。
simhash算法與随機超平面hash是怎麼聯系起來的呢？在simhash算法中，并沒有直接産生用于分割空間的随機向量，而是間接産生的：第 k個特征的hash簽名的第i位拿出來，如果為0，則改為-1，如果為1則不變，作為第i個随機向量的第k維。由于hash簽名是f位的，是以這樣能産生 f個随機向量，對應f個随機超平面。下面舉個例子：
假設用5個特征w1,…,w5來表示所有文檔，現要得到任意文檔的一個3維簽名。假設這5個特征對應的3維向量分别為：
h(w1) = (1, -1, 1)t
h(w2) = (-1, 1, 1)t
h(w3) = (1, -1, -1)t
h(w4) = (-1, -1, 1)t
h(w5) = (1, 1, -1)t
按simhash算法，要得到一個文檔向量d=(w1=1, w2=2, w3=0, w4=3, w5=0) t的簽名，
先要計算向量m = 1*h(w1) + 2*h(w2) + 0*h(w3) + 3*h(w4) + 0*h(w5) = (-4, -2, 6) t，然後根據simhash算法的步驟3，得到最終的簽名s=001。上面的計算步驟其實相當于，先得到3個5維的向量，第1個向量由h(w1),…,h(w5)的第1維組成：r1=(1,-1,1,-1,1)
t；第2個5維向量由h(w1),…,h(w5)的第2維組成：r2=(-1,1,-1,-1,1) t；同理，第3個5維向量為：r3=(1,1,-1,1,-1)
t.按随機超平面算法的步驟2，分别求向量d與r1,r2,r3的點積:
d t r1=-4 < 0，是以s1=0;
d t r2=-2 < 0，是以s2=0;
d t r3=6 > 0，是以s3=1.
故最終的簽名s=001，與simhash算法産生的結果是一緻的。
從上面的計算過程可以看出，simhash算法其實與随機超平面hash算法是相同的，simhash算法得到的兩個簽名的漢明距離，可以用來衡量原始向量的夾角。這其實是一種降維技術，将高維的向量用較低次元的簽名來表征。衡量兩個内容相似度，需要計算漢明距離，這對給定簽名查找相似内容的應用來說帶來了一些計算上的困難；我想，是否存在更為理想的simhash算法，原始内容的差異度，可以直接由簽名值的代數差來表示呢？
參考http://blog.sina.com.cn/s/blog_72995dcc010145ti.html
例如，文本的特征可以選取分詞結果，而權重可以用df來近似。
simhash具有兩個“沖突的性質”：
1. 它是一個hash方法
2. 相似的文本具有相似的hash值，如果兩個文本的simhash越接近，也就是漢明距離越小，文本就越相似。
是以海量文本中查重的任務轉換位如何在海量simhash中快速确定是否存在漢明距離小的指紋。也就是：在n個f-bit的指紋中，查詢漢明距離小于k的指紋。
在文章的實驗中，simhash采用64位的哈希函數。在80億網頁規模下漢明距離=3剛好合适。
是以任務的f-bit=64 , k=3 , n= 8*10^11
任務清晰，首先看一下兩種很直覺的方法：
1. 枚舉出所有漢明距離小于3的simhash指紋，對每個指紋在80億排序指紋中查詢。（這種方法需要進行c（64，3）=41664詞的simhash指紋，再為每個進行一次查詢）
2. 所有接近的指紋排序到一起，這至多有41664排序可能，需要龐大的空間。提出的方法介于兩者之間，合理的空間和時間的折中。
假設我們有一個已經排序的容量為2d，f-bit指紋集。看每個指紋的高d位。該高低位具有以下性質：盡管有很多的2d位組合存在，但高d位中有隻有少量重複的。
現在找一個接近于d的數字d’，由于整個表是排好序的，是以一趟搜尋就能找出高d’位與目标指紋f相同的指紋集合f’。因為d’和d很接近，是以找出的集合f’也不會很大。
最後在集合f’中查找 和f之間海明距離為k的指紋也就很快了。
總的思想：先要把檢索的集合縮小，然後在小集合中檢索f-d’位的海明距離
按照例子，80億網頁 有2^34 個，那麼理論上34位就能表示完80億不重複的指紋。我們假設最前的34位的表示完了80億指紋，假設指紋在前30位是一樣的，那麼後面4位還可以表示24個， 隻需要逐一比較這16個指紋是否于待測指紋漢明距離小于3。
假設：對任意34位中的30位都可以這麼做。
是以在一次完整的查找中，限定前q位精确比對（假設這些指紋已經是q位有序的，可以采用二分查找，如果指紋量非常大，且分布均勻，甚至可以采用内插搜尋），之後的2d-q個指紋剩下64-q位需要比較漢明距離小于3。
于是問題就轉變為如何切割64位的q。
将64位平分成若幹份，例如4份abcd，每份16位。
假設這些指紋已經按a部分排序好了，我們先按a的16位精确比對到一個區間，這個區間的後bcd位檢查漢明距離是否小于3。
同樣的假設，其次我們按b的16位精确比對到另一個區間，這個區間的所有指紋需要在acd位上比較漢明距離是否小于3。
同理還有c和d，是以這裡我們需要将全部的指紋t複制4份， t1 t2 t3 t4， t1按a排序，t2按b排序… 4份可以并行進行查詢，最後把結果合并。這樣即使最壞的情況：3個位分别落在其中3個區域abc,acd,bcd,abd…都不會被漏掉。
隻精确比對16位，還需要逐一比較的指紋量依然龐大，可能達到2d-16個，我們也可以精确比對更多的。
例如：将64位平分成4份abcd，每份16位，在bcd的48位上，我們再分成4份，wxzy，每份12位， 漢明距離的3位可以散落在任意三塊，那麼a與wxzy任意一份合起來做精确的28位…剩下3份用來檢查漢明距離。 同理b，c，d也可以這樣，那麼t需要複制16次，abcd與wxyz的組合做精确比對，每次精确比對後還需要逐一比較的個數降低到2d-28個。不同的組合方式也就是時間和空間上的權衡。
最壞情況是其中3份可能有1位漢明距離差異為1。
算法的描述如下：
1）先複制原表t為tt份：t1,t2,….tt
2）每個ti都關聯一個pi和一個πi，其中pi是一個整數, πi是一個置換函數，負責把pi個bit位換到高位上。
3）應用置換函數πi到相應的ti表上，然後對ti進行排序
4）然後對每一個ti和要比對的指紋f、海明距離k做如下運算：
a) 然後使用f’的高pi位檢索，找出ti中高pi位相同的集合
b) 在檢索出的集合中比較f-pi位，找出海明距離小于等于k的指紋
5）最後合并所有ti中檢索出的結果
由于文本已經壓縮成8個位元組了，是以其實simhash近似查重精度并不高：
筆者注：這個方法是第二次看了，還是不甚了解........講解不夠直覺明了..........
熬夜感覺并不好，如何才能戒掉這個壞習慣。
谷歌真叼......
筆者會在下一篇博文裡探讨simhash和vsm與重複網頁刪除偵測。
探讨資訊檢索與跳躍表。
探讨二分圖最大權比對（這個應用比較廣吧，感覺可以用來精确投放廣告，靈感來自計算機121教師和課程互選）。
http://blog.sina.com.cn/s/blog_72995dcc010145ti.html
http://gemantic.iteye.com/blog/1701101
http://blog.csdn.net/lgnlgn/article/details/6008498
http://blog.csdn.net/meijia_tts/article/details/7928579
論文detecting near-duplicates for web crawling.