數據搜索演算法

A. 查找演算法的作用

查找就是在一個數據集合里查找到你需要的數據，查找演算法就是在查找過程中使用的演算法。查找演算法有好多，最基礎的就是線性表查找。
因為提到了演算法，所以需要注意的是時間復雜度跟空間復雜度，進而涉及到數據的存儲方式，比如數組，鏈表，矩陣，樹，圖等等數據結構，這些數據結構可以幫助你降低演算法的復雜度。
如果有興趣，隨便找本數據結構書翻翻，裡面或多或少都會有講解。用關鍵字標識一個數據元素，查找時根據給定的某個值，在表中確定一個關鍵字的值等於給定值的記錄或數據元素。在計算機中進行查找的方法是根據表中的記錄的組織結構確定的。順序查找也稱為線形查找，從數據結構線形表的一端開始，順序掃描，依次將掃描到的結點關鍵字與給定值k相比較，若相等則表示查找成功；若掃描結束仍沒有找到關鍵字等於k的結點，表示查找失敗。二分查找要求線形表中的結點按關鍵字值升序或降序排列，用給定值k先與中間結點的關鍵字比較，中間結點把線形表分成兩個子表，若相等則查找成功；若不相等，再根據k與該中間結點關鍵字的比較結果確定下一步查找哪個子表，這樣遞歸進行，直到查找到或查找結束發現表中沒有這樣的結點。分塊查找也稱為索引查找，把線形分成若干塊，在每一塊中的數據元素的存儲順序是任意的，但要求塊與塊之間須按關鍵字值的大小有序排列，還要建立一個按關鍵字值遞增順序排列的索引表，索引表中的一項對應線形表中的一塊，

B. 大數據核心演算法有哪些

1、A* 搜索演算法——圖形搜索演算法，從給定起點到給定終點計算出路徑。其中使用了一種啟發式的估算，為每個節點估算通過該節點的最佳路徑，並以之為各個地點排定次序。演算法以得到的次序訪問這些節點。因此，A*搜索演算法是最佳優先搜索的範例。
2、集束搜索(又名定向搜索，Beam Search)——最佳優先搜索演算法的優化。使用啟發式函數評估它檢查的每個節點的能力。不過，集束搜索只能在每個深度中發現最前面的m個最符合條件的節點，m是固定數字——集束的寬度。

3、二分查找(Binary Search)——在線性數組中找特定值的演算法，每個步驟去掉一半不符合要求的數據。

4、分支界定演算法(Branch and Bound)——在多種最優化問題中尋找特定最優化解決方案的演算法，特別是針對離散、組合的最優化。

5、Buchberger演算法——一種數學演算法，可將其視為針對單變數最大公約數求解的歐幾里得演算法和線性系統中高斯消元法的泛化。

6、數據壓縮——採取特定編碼方案，使用更少的位元組數(或是其他信息承載單元)對信息編碼的過程，又叫來源編碼。

7、Diffie-Hellman密鑰交換演算法——一種加密協議，允許雙方在事先不了解對方的情況下，在不安全的通信信道中，共同建立共享密鑰。該密鑰以後可與一個對稱密碼一起，加密後續通訊。

8、Dijkstra演算法——針對沒有負值權重邊的有向圖，計算其中的單一起點最短演算法。

9、離散微分演算法(Discrete differentiation)。

C. 數據結構中關於數據查詢的演算法有哪些

數據查詢分靜態查找和動態查找：
靜態查找有：順序查找、有順序表的折半查找、分塊查
動態查找主要用二叉排序數查找。
哈希表 常用的哈希函數有；直接定址法，除留余數法，數字分析法，平方取中法，折疊法。

一般情況下這些就夠用了

D. 全文檢索演算法，請問誰能給我點頭緒落，不懂啊。。

全文檢索技術
全文檢索是指索引程序掃描文章中的每個詞並建立對應索引，記錄該詞出現的位置和次數。當通過搜索引擎查詢時，檢索程序就在記錄的索引進行查找並返回給用戶。全文檢索又分為基於字的全文索引和基於詞的全文索引。基於字的全文索引會對內容中的每個字建立索引並記錄，此方法查全率高，但查准率低，特別是對於中文，有時搜索馬克，會列出馬克思的結果。基於詞的全文索引是把一個詞語作為一個單位進行索引記錄，並能處理同義詞。搜索引擎有自己的詞庫，當用戶搜索時，搜索引擎會從詞庫中抽取關鍵詞作為索引項，這樣可以大大提高檢索的准確率。
中文分詞技術
一直以來大家都比較熟悉網路，網路有自己的中文分詞技術。一般採用的包括正向最大匹配，反向最大匹配，最佳匹配法，專家系統方法等。其中最大正向匹配是最常用的分詞解決方案，它採用機械式演算法，通過建立詞典並進行正向最大匹配對中文進行分詞。舉個簡單的例子比如搜索「北京大學在哪裡」，則返回結果很多都是包含北京大學，北大等詞語的網頁，搜索引擎就是採用正向最大匹配去判斷，把北京大學當做一個詞語來索引記錄並返回。當然，正向最大匹配也有不完整性，比如長度過長的詞語，搜索引擎有時無法准確的分詞，或者對前後都相互關聯的詞無法准確分詞。例如「結合成分子時」，會被返回結合、成分、子時，而有時我們想要的關鍵詞是「分子」。
很多時候網路都會根據自己詞庫中詞語的權重進行拆分，權重的計算基於生活各個方面，比較復雜，搜索引擎要做的就是返回用戶最想要的結果，有時站長們做網站要站在用戶的角度去考慮問題，其實這也是站在搜索引擎的角度考慮問題，不論在確定目標關鍵詞或者是長尾關鍵詞時，都可以根據中文分詞的原理來選擇，這樣可以最大化的減少無用功。
分詞原理不斷在變化，不斷在更新，我們應該繼續學習，只有掌握了本質才能抓住實質。

E. 基於資料庫搜索的演算法，關鍵有哪幾點

B+、B- Tree(mysql,oracle,mongodb)
主要用在關系資料庫的索引中，如oracle，mysql innodb；mongodb中的索引也是B-樹實現的；還有HBase中HFile中的DataBlock的索引等等。
動態查找樹主要有：二叉查找樹（Binary Search Tree），平衡二叉查找樹（Balanced Binary Search Tree），紅黑樹(Red-Black Tree )，B-tree/B+-tree/ B*-tree (B~Tree)。前三者是典型的二叉查找樹結構，其查找的時間復雜度O(log2N)與樹的深度相關，那麼降低樹的深度自然會提高查找效率。
但是咱們有面對這樣一個實際問題：就是大規模數據存儲中，實現索引查詢這樣一個實際背景下，樹節點存儲的元素數量是有限的（如果元素數量非常多的話，查找就退化成節點內部的線性查找了），這樣導致二叉查找樹結構由於樹的深度過大而造成磁碟I/O讀寫過於頻繁，進而導致查詢效率低下，那麼如何減少樹的深度（當然是不能減少查詢的數據量），一個基本的想法就是：採用多叉樹結構（由於樹節點元素數量是有限的，自然該節點的子樹數量也就是有限的）。
也就是說，因為磁碟的操作費時費資源，如果過於頻繁的多次查找勢必效率低下。那麼如何提高效率，即如何避免磁碟過於頻繁的多次查找呢？根據磁碟查找存取的次數往往由樹的高度所決定，所以，只要我們通過某種較好的樹結構減少樹的結構盡量減少樹的高度，那麼是不是便能有效減少磁碟查找存取的次數呢？那這種有效的樹結構是一種怎樣的樹呢？
這樣我們就提出了一個新的查找樹結構——多路查找樹。根據平衡二叉樹的啟發，自然就想到平衡多路查找樹結構，也就是B~tree，即B樹結構(後面，我們將看到，B樹的各種操作能使B樹保持較低的高度，從而達到有效避免磁碟過於頻繁的查找存取操作，從而有效提高查找效率)。

Hash表+桶(redis)
mysql中的adaptive hash index，redis中的數據存儲實現都是採用hash，可以高效的進行數據的查詢。
哈希表（Hash table，也叫散列表），是根據關鍵碼值(Key value)而直接進行訪問的數據結構。也就是說，它通過把關鍵碼值映射到表中一個位置來訪問記錄，以加快查找的速度。這個映射函數叫做散列函數，存放記錄的數組叫做散列表。
哈希表的做法其實很簡單，就是把Key通過一個固定的演算法函數既所謂的哈希函數轉換成一個整型數字，然後就將該數字對數組長度進行取余，取余結果就當作數組的下標，將value存儲在以該數字為下標的數組空間里。
而當使用哈希表進行查詢的時候，就是再次使用哈希函數將key轉換為對應的數組下標，並定位到該空間獲取value，如此一來，就可以充分利用到數組的定位性能進行數據定位
數組的特點是：定址容易，插入和刪除困難；而鏈表的特點是：定址困難，插入和刪除容易。綜合兩者特性，設計一種定址容易，插入刪除也容易的數據結構，如拉鏈法實現的哈希表。

Booleam Filter（HBase）
HBase中的rowkey設置建立Booleam Filter映射，用於快速判斷rowkey是否在一個HFile中。在分布式資料庫中用的比較多。
基於BitMap的存儲結構，採用的是哈希函數的方法，將一個元素映射到一個 m 長度的陣列上的一個點，當這個點是 1 時，那麼這個元素在集合內，反之則不在集合內。這個方法的缺點就是當檢測的元素量很多時候可能有沖突，解決方法就是使用 k 個哈希 函數對應 k 個點，如果所有點都是 1 的話，那麼元素在集合內，如果有 0 的話，元素則不再集合內。

F. 常見的數據檢索演算法有哪些資料庫都採用什麼樣的檢索方式如何提高檢索的效率

信息檢索方法包括：普通法、追溯法和分段法。1、普通法是利用書目、文摘、索引等檢索工具進行文獻資料查找的方法。運用這種方法的關鍵在於熟悉各種檢索工具的性質、特點和查找過程，從不同角度查找。普通法又可分為順檢法和倒檢法。2、追溯法是利用已有文獻所附的參考文獻不斷追蹤查找的方法，在沒有檢索工具或檢索工具不全時，此法可獲得針對性很強的資料，查准率較高，查全率較差。3、分段法是追溯法和普通法的綜合，它將兩種方法分期、分段交替使用，直至查到所需資料為止。(6)數據搜索演算法擴展閱讀檢索原因信息檢索是獲取知識的捷徑美國普林斯頓大學物理系一個年輕大學生名叫約瀚·菲利普，在圖書館里借閱有關公開資料，僅用四個月時間，就畫出一張製造原子彈的設計圖。他設計的原子彈，體積小(棒球大小)、重量輕(7.5公斤)、威力大(相當廣島原子彈3/4的威力)，造價低(當時僅需兩千美元)，致使一些國家（法國、巴基斯坦等）紛紛致函美國大使館，爭相購買他的設計拷貝。二十世紀七十年代，美國核專家泰勒收到一份題為《製造核彈的方法》的報告，他被報告精湛的技術設計所吸引，驚嘆地說：「至今我看到的報告中，它是最詳細、最全面的一份。」

G. 數據查找的常見數據查找方法

對於隨機文件，如果是計算定址結構的文件可以採用直接查找的方法，即利用關鍵字值和記錄位置之間的對應關系直接找到該絕態磨記錄。如果是索引結構的並鬥文件，先用上述方法查找索引，在索引中找到相應關鍵字值後，再由索引表上對應的地址找到相應的記錄。不同查找方法的效率很不相同，這主要取決於文件結構和查詢問題的特點，查詢演算法本身也閉圓是重要影響因素。

H. 數據的演算法都有哪些……

A*搜尋演算法
俗稱A星演算法。這是一種在圖形平面上，有多個節點的路徑，求出最低通過成本的演算法。常用於游戲中的 NPC的移動計算，或線上游戲的 BOT的移動計算上。該演算法像 Dijkstra演算法一樣，可以找到一條最短路徑；也像BFS一樣，進行啟發式的搜索。

Beam Search
束搜索(beam search)方法是解決優化問題的一種啟發式方法，它是在分枝定界方法基礎上發展起來的，它使用啟發式方法估計k個最好的路徑，僅從這k個路徑出發向下搜索，即每一層只有滿意的結點會被保留，其它的結點則被永久拋棄，從而比分枝定界法能大大節省運行時間。束搜索於20 世紀70年代中期首先被應用於 人工智慧領域,1976 年Lowerre在其稱為 HARPY的語音識別系統中第一次使用了束搜索方法。他的目標是並行地搜索幾個潛在的最優決策路徑以減少回溯，並快速地獲得一個解。

二分取中查找演算法
一種在有序數組中查找某一特定元素的搜索演算法。搜素過程從數組的中間元素開始，如果中間元素正好是要查找的元素，則搜素過程結束；如果某一特定元素大於或者小於中間元素，則在數組大於或小於中間元素的那一半中查找，而且跟開始一樣從中間元素開始比較。這種搜索演算法每一次比較都使搜索范圍縮小一半。

Branch and bound
分支定界演算法是一種在問題的解空間樹上搜索問題的解的方法。但與回溯演算法不同，分支定界演算法採用廣度優先或最小耗費優先的方法搜索解空間樹，並且，在分支定界演算法中，每一個活結點只有一次機會成為擴展結點。

數據壓縮
數據壓縮是通過減少計算機中所存儲數據或者通信傳播中數據的冗餘度，達到增大數據密度，最終使數據的存儲空間減少的技術。數據壓縮在文件存儲和分布式系統領域有著十分廣泛的應用。數據壓縮也代表著尺寸媒介容量的增大和網路帶寬的擴展。

Diffie–Hellman密鑰協商
Diffie–Hellman key exchange，簡稱「D–H」，是一種安全協議。它可以讓雙方在完全沒有對方任何預先信息的條件下通過不安全信道建立起一個密鑰。這個密鑰可以在後續的通訊中作為對稱密鑰來加密通訊內容。

Dijkstra』s 演算法
迪科斯徹演算法（Dijkstra）是由荷蘭計算機科學家艾茲格·迪科斯徹發明的。演算法解決的是有向圖中單個源點到其他頂點的最短路徑問題。舉例來說，如果圖中的頂點表示城市，而邊上的權重表示著城市間開車行經的距離，迪科斯徹演算法可以用來找到兩個城市之間的最短路徑。

動態規劃
動態規劃是一種在 數學和計算機科學中使用的，用於求解包含重疊子問題的最優化問題的方法。其基本思想是，將原問題分解為相似的子問題，在求解的過程中通過子問題的解求出原問題的解。 動態規劃的思想是多種演算法的基礎，被廣泛應用於計算機科學和工程領域。比較著名的應用實例有：求解最短路徑問題，背包問題，項目管理，網路流優化等。這里也有一篇文章說得比較詳細。

歐幾里得演算法
在 數學中，輾轉相除法，又稱 歐幾里得演算法，是求 最大公約數的演算法。輾轉相除法首次出現於 歐幾里得的《幾何原本》（第VII卷，命題i和ii）中，而在中國則可以追溯至 東漢出現的《九章算術》。

快速傅里葉變換(FFT)
快速傅里葉變換（Fast Fourier Transform，FFT），是離散傅里葉變換的快速演算法，也可用於計算離散傅里葉變換的逆變換。快速傅里葉變換有廣泛的應用，如數字信號處理、計算大整數乘法、求解偏微分方程等等。

哈希函數
HashFunction是一種從任何一種數據中創建小的數字「指紋」的方法。該 函數將數據打亂混合，重新創建一個叫做散列值的指紋。散列值通常用來代表一個短的隨機字母和數字組成的字元串。好的散列 函數在輸入域中很少出現散列沖突。在散列表和數據處理中，不抑制沖突來區別數據，會使得資料庫記錄更難找到。

堆排序
Heapsort是指利用堆積樹（堆）這種 數據結構所設計的一種排序演算法。堆積樹是一個近似完全二叉樹的結構，並同時滿足堆積屬性：即子結點的鍵值或索引總是小於（或者大於）它的父結點。

歸並排序
Merge sort是建立在歸並操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

RANSAC 演算法
RANSAC 是」RANdom SAmpleConsensus」的縮寫。該演算法是用於從一組觀測數據中估計 數學模型參數的迭代方法，由Fischler and Bolles在1981提出，它是一種非確定性演算法，因為它只能以一定的概率得到合理的結果，隨著迭代次數的增加，這種概率是增加的。該演算法的基本假設是觀測數據集中存在」inliers」（那些對模型參數估計起到支持作用的點）和」outliers」（不符合模型的點），並且這組觀測數據受到雜訊影響。RANSAC 假設給定一組」inliers」數據就能夠得到最優的符合這組點的模型。

RSA加密演演算法
這是一個公鑰加密演算法，也是世界上第一個適合用來做簽名的演算法。今天的RSA已經 專利失效，其被廣泛地用於 電子商務加密，大家都相信，只要密鑰足夠長，這個演算法就會是安全的。

並查集Union-find
並查集是一種樹型的 數據結構，用於處理一些不相交集合（Disjoint Sets）的合並及查詢問題。常常在使用中以森林來表示。

Viterbi algorithm
尋找最可能的隱藏狀態序列
等等這些，演算法很多。

I. 數據結構中有哪些查找演算法

和二分查找性能接近的：既然可以二分查找，那麼關鍵字肯定可以滿足全序關系。那麼可以用二叉查找樹，一般的就是平攤O(logn),最壞O(n)。如果用平衡樹，如AVL,Treap,Splay等等，可以做到保持O(logn)的界。
比二分查找性能更優的：大概只有Hash了吧。如果Hash函數設計的好，基本可以認為是O(1)的。這個你最好系統學習一下，尤其是字元串的Hash函數。

J. 數據結構：重要的查找演算法有哪些

折半查找也就是二分查找，它必須滿足排序關系。
查找也可以用二叉查找樹，一般復雜度為O(logn),最壞為O(n)。
也可用平衡樹進行查找，如AVL,Treap,Splay等，可以做到保持O(logn)。

比二分查找性能更優的：大概只有Hash了吧。如果Hash函數設計的好，基本可以認為是O(1)

堆排序比較有意思，值得研究一下，理解了後，很有用～，也很重要。