倒排索引

倒排索引(Inverted Index)：

站在用戶的角度思考問(wèn)題，與客戶深入溝通，找到臨潭網(wǎng)站設(shè)計(jì)與臨潭網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類型包括：成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、域名與空間、網(wǎng)站空間、企業(yè)郵箱。業(yè)務(wù)覆蓋臨潭地區(qū)。

倒排索引從邏輯結(jié)構(gòu)和基本思路上講非常簡(jiǎn)單，下面我們通過(guò)具體實(shí)例來(lái)進(jìn)行說(shuō)明，使得大家能夠?qū)Φ古潘饕幸粋€(gè)宏觀而直接的感受。

中文和英文等語(yǔ)言不同，單詞之間沒(méi)有明確的分隔符號(hào)，所以首先要用分詞系統(tǒng)將文檔自動(dòng)切分成單詞序列，這樣每個(gè)文檔就轉(zhuǎn)換為由單詞序列構(gòu)成的數(shù)據(jù)流。

為了系統(tǒng)后續(xù)處理方便，需要對(duì)每個(gè)不同的單詞賦予唯一的單詞編號(hào)，同時(shí)記錄下哪些文檔包含這個(gè)單詞，在處理結(jié)束后，我們可以得到最簡(jiǎn)單的倒排索引（參考圖4）。

圖4中，“單詞ID”一列記錄了每個(gè)單詞對(duì)應(yīng)的編號(hào)，第2列是對(duì)應(yīng)的單詞，第3列即每個(gè)單詞對(duì)應(yīng)的倒排列表。比如：?jiǎn)卧~“谷歌”，其中單詞編號(hào)為1，倒排列表為{1,2,3,4,5}，說(shuō)明文檔集合中每個(gè)文檔都包含了這個(gè)單詞。

之所以說(shuō)圖4的倒排索引是最簡(jiǎn)單的，是因?yàn)檫@個(gè)索引系統(tǒng)只記載了哪些文檔包含某個(gè)單詞。而事實(shí)上，索引系統(tǒng)還可以記錄除此之外的更多信息。

圖5是一個(gè)相對(duì)復(fù)雜些的倒排索引，與圖4所示的基本索引系統(tǒng)相比，在單詞對(duì)應(yīng)的倒排列表中不僅記錄了文檔編號(hào)，還記載了單詞頻率信息，即這個(gè)單詞在某個(gè)文檔中出現(xiàn)的次數(shù)。之所以要記錄這個(gè)信息，是因?yàn)樵~頻信息在搜索結(jié)果排序時(shí)，計(jì)算查詢和文檔相似度是一個(gè)很重要的計(jì)算因子，所以將其記錄在倒排列表中，以方便后續(xù)排序時(shí)進(jìn)行分值計(jì)算。

在圖5所示的例子里，單詞“創(chuàng)始人”的單詞編號(hào)為7，對(duì)應(yīng)的倒排列表內(nèi)容有（3;1），其中3代表文檔編號(hào)為3的文檔包含這個(gè)單詞，數(shù)字1代表詞頻信息，即這個(gè)單詞在3號(hào)文檔中只出現(xiàn)過(guò)1次，其他單詞對(duì)應(yīng)的倒排列表所代表的含義與此相同。

實(shí)用的倒排索引還可以記載更多的信息，圖6所示的索引系統(tǒng)除了記錄文檔編號(hào)和單詞詞頻信息外，額外記載了兩類信息——即每個(gè)單詞對(duì)應(yīng)的文檔頻率信息（圖6的第3列）及單詞在某個(gè)文檔出現(xiàn)位置的信息。

文檔頻率信息代表了在文檔集合中有多少個(gè)文檔包含某個(gè)單詞，之所以要記錄這個(gè)信息，其原因與單詞頻率信息一樣，這個(gè)信息在搜索結(jié)果排序計(jì)算中是一個(gè)非常重要的因子。

而單詞在某個(gè)文檔中出現(xiàn)位置的信息并非索引系統(tǒng)一定要記錄的，在實(shí)際的索引系統(tǒng)里可以包含，也可以選擇不包含這個(gè)信息，之所以如此，是因?yàn)檫@個(gè)信息對(duì)于搜索系統(tǒng)來(lái)說(shuō)并非必要，位置信息只有在支持短語(yǔ)查詢的時(shí)候才能夠派上用場(chǎng)。

以單詞“拉斯”為例：其單詞編號(hào)為8，文檔頻率為2，代表整個(gè)文檔集合中有兩個(gè)文檔包含這個(gè)單詞，對(duì)應(yīng)的倒排列表為{(3;1;4),(5;1;4)}，其含義為在文檔3和文檔5出現(xiàn)過(guò)這個(gè)單詞，單詞頻率都為1，單詞“拉斯”在這兩個(gè)文檔中的出現(xiàn)位置都是4，即文檔中第4個(gè)單詞是“拉斯”。

圖6所示的倒排索引已經(jīng)是一個(gè)非常完備的索引系統(tǒng)，實(shí)際搜索引擎的索引結(jié)構(gòu)基本如此，區(qū)別無(wú)非是采取哪些具體的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)上述邏輯結(jié)構(gòu)。

有了這個(gè)索引系統(tǒng)，搜索引擎可以很方便地響應(yīng)用戶的查詢。比如：用戶輸入查詢?cè)~ “Facebook”，搜索系統(tǒng)查找倒排索引，從中可用讀出包含這個(gè)單詞的文檔，這些文檔就是提供給用戶的搜索結(jié)果。

而利用單詞詞頻信息、文檔頻率信息即可對(duì)這些候選搜索結(jié)果進(jìn)行排序，計(jì)算文檔和查詢的相似性，按照相似性得分由高到低排序輸出，此即為搜索系統(tǒng)的部分內(nèi)部流程。

單詞詞典是倒排索引中非常重要的組成部分，它用來(lái)維護(hù)文檔集合中出現(xiàn)過(guò)的 所有單詞 的相關(guān)信息，同時(shí)用來(lái)記載某個(gè) 單詞對(duì)應(yīng)的倒排列表在倒排文件中的位置信息 。在支持搜索時(shí)，根據(jù)用戶的查詢?cè)~，去單詞詞典里查詢，就能夠獲得相應(yīng)的倒排列表，并以此作為后續(xù)排序的基礎(chǔ)。

對(duì)于一個(gè)規(guī)模很大的文檔集合來(lái)說(shuō)，可能包含幾十萬(wàn)甚至上百萬(wàn)的不同單詞，能否快速定位某個(gè)單詞，這直接影響搜索時(shí)的響應(yīng)速度，所以需要高效的數(shù)據(jù)結(jié)構(gòu)來(lái)對(duì)單詞詞典進(jìn)行構(gòu)建和查找， 常用的數(shù)據(jù)結(jié)構(gòu)包括 哈希加鏈表 結(jié)構(gòu)和 樹(shù)形 詞典結(jié)構(gòu)。

B樹(shù)（或者B+樹(shù)）是另外一種高效查找結(jié)構(gòu)，圖8是一個(gè) B樹(shù)結(jié)構(gòu)示意圖。B樹(shù)與哈希方式查找不同，需要字典項(xiàng)能夠按照大小排序（數(shù)字或者字符序），而哈希方式則無(wú)須數(shù)據(jù)滿足此項(xiàng)要求。

B樹(shù)形成了層級(jí)查找結(jié)構(gòu)，中間節(jié)點(diǎn)用于指出一定順序范圍的詞典項(xiàng)目存儲(chǔ)在哪個(gè)子樹(shù)中，起到根據(jù)詞典項(xiàng)比較大小進(jìn)行導(dǎo)航的作用，最底層的葉子節(jié)點(diǎn)存儲(chǔ)單詞的地址信息，根據(jù)這個(gè)地址就可以提取出單詞字符串。

具體的大家可以看看[ ;fps=1 )

java請(qǐng)隨機(jī)輸入10個(gè)數(shù)字保存到List中,并按倒序顯示出來(lái)

smile_bug 說(shuō)的這個(gè)我還真沒(méi)想過(guò)，想想覺(jué)得很行啊

找了手冊(cè)，才知道java的list沒(méi)tree的，懶得寫(xiě)個(gè)，汗

那只能二樓的方法

public static void main(final String[] args) {

final ListInteger integers = new ArrayListInteger();

final Scanner scanner = new Scanner(System.in);

for (int i = 1; i = 3; i++) {

try {

System.out.println("輸入第" + i + "個(gè)數(shù)吧");

final int input = Integer.parseInt(scanner.next());

integers.add(input);

}

catch (final Throwable e) {

System.err.println("這不是個(gè)數(shù)字，我可是超級(jí)程序");

i--;

continue;

}

}

Collections.sort(integers);// 自然排

Collections.reverse(integers);// 倒排

for (final Integer integer : integers) {

System.out.println(integer);

}

}

java代碼轉(zhuǎn)時(shí)序圖或抽象語(yǔ)義樹(shù) ，下面是java代碼

System.Security.Cryptography.SHA512 shaM = new System.Security.Cryptography.SHA512Managed(); 是個(gè)類是.net的類，要java中也有相關(guān)類要自己去寫(xiě)。

JAVA編程問(wèn)題求助 編寫(xiě)程序，把一個(gè)數(shù)組中的元素倒過(guò)來(lái)。例如原數(shù)組為1，2，3，4，5。則倒排

import?java.util.*;

import?static?java.lang.System.*;

import?static?java.util.Arrays.*;

public?class?Test

{

public?static?void?main(String[]?args)

{

Integer[]?array={1,2,3,4,5};

//數(shù)組工具類的排列方法，我開(kāi)始嘗試使用Lambda表達(dá)式但是失敗了

sort(array,new?ComparatorInteger()

{

public?int?compare(Integer?a,Integer?b)

{

//如果a大于b返回a小于b，反之亦然，造成倒序排列的效果

return?ab?-1:ab?1:0;

}

});

//輸出排列后的數(shù)組，輸出"[5,?4,?3,?2,?1]"

out.println(Arrays.toString(array));

}

}