什么是倒排索引？

倒排索引（英語：Inverted index），也常被稱為反向索引、置入檔案或反向檔案，是一種索引方法，被用來存儲(chǔ)在全文搜索下某個(gè)單詞在一個(gè)文檔或者一組文檔中的存儲(chǔ)位置的映射。它是文檔檢索系統(tǒng)中最常用的數(shù)據(jù)結(jié)構(gòu)。通過倒排索引，可以根據(jù)單詞快速獲取包含這個(gè)單詞的文檔列表。倒排索引主要由兩個(gè)部分組成：“單詞詞典”和“倒排文件”。

假設(shè)我們現(xiàn)在有文件：

test1.txt中存有：我們愛自然語言處理

test2.txt中存有：我們愛計(jì)算機(jī)視覺

正向索引：

{“test1.txt”:["我們",“愛”,"自然語言","處理"],"test2.txt":["我們","愛","計(jì)算機(jī)","視覺"]}

那么，我們應(yīng)該如何通過正向索引找到包含某詞語的文件呢？我們只能依次遍歷文件中的內(nèi)容，從內(nèi)容中找到是否有該詞語，正向查詢的效率很低。

倒排索引：

{"我們":["test1.txt","test2.txt"],"愛":["test1.txt","test2.txt"],"自然語言":["test1.txt"],"處理":["test1.txt"],"計(jì)算機(jī)":["test2.txt"],"視覺":["test2.txt"]}

建立倒排索引后，我們要想查找包含某些單詞的文件，直接從hash表中獲取，是不是就方便多了？接下來，我們用python實(shí)現(xiàn)：

現(xiàn)在有基本目錄：

python.txt

Python的設(shè)計(jì)哲學(xué)是“優(yōu)雅”、“明確”、“簡單”。因此，Perl語言中“總是有多種方法來做同一件事”的理念在Python開發(fā)者中通常是難以忍受的。Python開發(fā)者的哲學(xué)是“用一種方法，最好是只有一種方法來做一件事”。在設(shè)計(jì)Python語言時(shí)，如果面臨多種選擇，Python開發(fā)者一般會(huì)拒絕花俏的語法，而選擇明確的沒有或者很少有歧義的語法。由于這種設(shè)計(jì)觀念的差異，Python源代碼通常被認(rèn)為比Perl具備更好的可讀性，并且能夠支撐大規(guī)模的軟件開發(fā)。這些準(zhǔn)則被稱為Python格言。在Python解釋器內(nèi)運(yùn)行import this可以獲得完整的列表。
Python開發(fā)人員盡量避開不成熟或者不重要的優(yōu)化。一些針對(duì)非重要部位的加快運(yùn)行速度的補(bǔ)丁通常不會(huì)被合并到Python內(nèi)。所以很多人認(rèn)為Python很慢。不過，根據(jù)二八定律，大多數(shù)程序?qū)λ俣纫蟛桓摺Ｔ谀承?duì)運(yùn)行速度要求很高的情況，Python設(shè)計(jì)師傾向于使用JIT技術(shù)，或者用使用C/C++語言改寫這部分程序。可用的JIT技術(shù)是PyPy。
Python是完全面向?qū)ο蟮恼Z言。函數(shù)、模塊、數(shù)字、字符串都是對(duì)象。并且完全支持繼承、重載、派生、多繼承，有益于增強(qiáng)源代碼的復(fù)用性。Python支持重載運(yùn)算符和動(dòng)態(tài)類型。相對(duì)于Lisp這種傳統(tǒng)的函數(shù)式編程語言，Python對(duì)函數(shù)式設(shè)計(jì)只提供了有限的支持。有兩個(gè)標(biāo)準(zhǔn)庫(functools, itertools)提供了Haskell和Standard ML中久經(jīng)考驗(yàn)的函數(shù)式程序設(shè)計(jì)工具。

java.txt

1.簡單性
Java看起來設(shè)計(jì)得很像C++，但是為了使語言小和容易熟悉，設(shè)計(jì)者們把C++語言中許多可用的特征去掉了，這些特征是一般程序員很少使用的。例如，Java不支持go to語句，代之以提供break和continue語句以及異常處理。Java還剔除了C++的操作符過載（overload）和多繼承特征，并且不使用主文件，免去了預(yù)處理程序。因?yàn)镴ava沒有結(jié)構(gòu)，數(shù)組和串都是對(duì)象，所以不需要指針。Java能夠自動(dòng)處理對(duì)象的引用和間接引用，實(shí)現(xiàn)自動(dòng)的無用單元收集，使用戶不必為存儲(chǔ)管理問題煩惱，能更多的時(shí)間和精力花在研發(fā)上。
2.面向?qū)ο?br /> Java是一個(gè)面向?qū)ο蟮恼Z言。對(duì)程序員來說，這意味著要注意應(yīng)中的數(shù)據(jù)和操縱數(shù)據(jù)的方法（method），而不是嚴(yán)格地用過程來思考。在一個(gè)面向?qū)ο蟮南到y(tǒng)中，類（class）是數(shù)據(jù)和操作數(shù)據(jù)的方法的集合。數(shù)據(jù)和方法一起描述對(duì)象（object）的狀態(tài)和行為。每一對(duì)象是其狀態(tài)和行為的封裝。類是按一定體系和層次安排的，使得子類可以從超類繼承行為。在這個(gè)類層次體系中有一個(gè)根類，它是具有一般行為的類。Java程序是用類來組織的。
Java還包括一個(gè)類的擴(kuò)展集合，分別組成各種程序包（Package），用戶可以在自己的程序中使用。例如，Java提供產(chǎn)生圖形用戶接口部件的類（java.awt包），這里awt是抽象窗口工具集（abstract windowing toolkit）的縮寫，處理輸入輸出的類（java.io包）和支持網(wǎng)絡(luò)功能的類（java.net包）。
3.分布性
Java設(shè)計(jì)成支持在網(wǎng)絡(luò)上應(yīng)用，它是分布式語言。Java既支持各種層次的網(wǎng)絡(luò)連接，又以Socket類支持可靠的流（stream）網(wǎng)絡(luò)連接，所以用戶可以產(chǎn)生分布式的客戶機(jī)和服務(wù)器。
網(wǎng)絡(luò)變成軟件應(yīng)用的分布運(yùn)載工具。Java程序只要編寫一次，就可到處運(yùn)行。

c.txt

C語言是一種結(jié)構(gòu)化語言，它有著清晰的層次，可按照模塊的方式對(duì)程序進(jìn)行編寫，十分有利于程序的調(diào)試，且c語言的處理和表現(xiàn)能力都非常的強(qiáng)大，依靠非常全面的運(yùn)算符和多樣的數(shù)據(jù)類型，可以輕易完成各種數(shù)據(jù)結(jié)構(gòu)的構(gòu)建，通過指針類型更可對(duì)內(nèi)存直接尋址以及對(duì)硬件進(jìn)行直接操作，因此既能夠用于開發(fā)系統(tǒng)程序，也可用于開發(fā)應(yīng)用軟件。通過對(duì)C語言進(jìn)行研究分析，總結(jié)出其主要特點(diǎn)如下：
（1）簡潔的語言
C語言包含有各種控制語句僅有9種，關(guān)鍵字也只有32 個(gè)，程序的編寫要求不嚴(yán)格且多以小寫字母為主，對(duì)許多不必要的部分進(jìn)行了精簡。實(shí)際上，語句構(gòu)成與硬件有關(guān)聯(lián)的較少，且C語言本身不提供與硬件相關(guān)的輸入輸出、文件管理等功能，如需此類功能，需要通過配合編譯系統(tǒng)所支持的各類庫進(jìn)行編程，故c語言擁有非常簡潔的編譯系統(tǒng)。 [5]
（2）具有結(jié)構(gòu)化的控制語句
C語言是一種結(jié)構(gòu)化的語言，提供的控制語句具有結(jié)構(gòu)化特征，如for語句、if⋯else語句和switch語句等。可以用于實(shí)現(xiàn)函數(shù)的邏輯控制，方便面向過程的程序設(shè)計(jì)。 [5]
（3）豐富的數(shù)據(jù)類型
C語言包含的數(shù)據(jù)類型廣泛，不僅包含有傳統(tǒng)的字符型、整型、浮點(diǎn)型、數(shù)組類型等數(shù)據(jù)類型，還具有其他編程語言所不具備的數(shù)據(jù)類型，其中以指針類型數(shù)據(jù)使用最為靈活，可以通過編程對(duì)各種數(shù)據(jù)結(jié)構(gòu)進(jìn)行計(jì)算。 [5]
（4）豐富的運(yùn)算符
C語言包含34個(gè)運(yùn)算符，它將賦值、括號(hào)等均視作運(yùn)算符來操作，使C程序的表達(dá)式類型和運(yùn)算符類型均非常豐富。 [5]
（5）可對(duì)物理地址進(jìn)行直接操作
C語言允許對(duì)硬件內(nèi)存地址進(jìn)行直接讀寫，以此可以實(shí)現(xiàn)匯編語言的主要功能，并可直接操作硬件。C語言不但具備高級(jí)語言所具有的良好特性，又包含了許多低級(jí)語言的優(yōu)勢，故在系統(tǒng)軟件編程領(lǐng)域有著廣泛的應(yīng)用。 [5]
（6）代碼具有較好的可移植性
C語言是面向過程的編程語言，用戶只需要關(guān)注所被解決問題的本身，而不需要花費(fèi)過多的精力去了解相關(guān)硬件，且針對(duì)不同的硬件環(huán)境，在用C語言實(shí)現(xiàn)相同功能時(shí)的代碼基本一致，不需或僅需進(jìn)行少量改動(dòng)便可完成移植，這就意味著，對(duì)于一臺(tái)計(jì)算機(jī)編寫的C程序可以在另一臺(tái)計(jì)算機(jī)上輕松地運(yùn)行，從而極大的減少了程序移植的工作強(qiáng)度。 [5]
（7）可生成的高質(zhì)量目標(biāo)代碼，高執(zhí)行效率的程序
復(fù)制代碼
首先，我們導(dǎo)入相應(yīng)的包：

#用于獲取該目錄下得所有txt文件，忽略掉文件夾及里面的
import glob
#主要是一些路徑的操作
import os
#對(duì)句子進(jìn)行分詞或關(guān)鍵詞提取
from jieba import analyse

接下來，我們要獲取所有txt文件的絕對(duì)路徑：

#獲取當(dāng)前pyhtho文件所在的目錄：當(dāng)前是：C:\gongoubo\python-work\direc\files
dir_path = os.path.dirname(os.path.abspath(__file__))
print(dir_path)
#存儲(chǔ)txt文件的絕對(duì)路徑為列表，同時(shí)為每個(gè)文件建立索引
def file_store():
    files_name =[]
    files_dict = {}
    #獲取file文件夾下所有為txt的文件
    for i,name in enumerate(glob.glob("file/*.txt")):
        files_dict[i] = name.split('\\')[-1]
        file_name = dir_path + "\\" + name
        files_name.append(file_name)
    return files_name,files_dict

然后，我們讀取每個(gè)txt文件，再對(duì)其進(jìn)行關(guān)鍵詞提取，將結(jié)果存儲(chǔ)到新的txt中，并用原txt文件的索引命名：

#讀取每個(gè)txt文件
def transform(files_name):
    #注意打開的時(shí)候需要申明為utf-8編碼
    for i,j in enumerate(files_name):
        #打開文件
        tmp = open(j,'r',encoding='utf-8').read()
        #提取關(guān)鍵詞
        content = analyse.extract_tags(tmp)
　　　　 #也可以進(jìn)行分詞content=jieba.cut_for_search(tmp)，關(guān)于jieba分詞，可以看我的自然語言處理之基礎(chǔ)技能
        #新建process文件夾
        path=dir_path+'\\file\\'+'process'
        if not os.path.exists(path):
            os.makedirs(path)
        #為存儲(chǔ)關(guān)鍵詞的txt取名，對(duì)應(yīng)這每個(gè)文件的索引
        fp=open(path+'\\'+str(i)+'.txt','w',encoding='utf-8')
        #將關(guān)鍵詞寫入到txt中
        fp.write(" ".join(content))
        fp.close()

運(yùn)行后，我們會(huì)有如下目錄：其中process文件夾下的是提取關(guān)鍵詞后的結(jié)果，文件名對(duì)應(yīng)索引，即{0:"c.txt",1:"java.txt",2:"python.txt"}

 接下來，進(jìn)行倒排索引的構(gòu)建：

#建立倒排索引
def invert_index():
 path=dir_path+'\\file\\'+'process'
 word_dict = {}
 # 取包含關(guān)鍵詞的txt
 for file in glob.glob(path+'/*.txt'):
  #取出txt文件名，也就是文件的索引
  index = file.split('\\')[-1][0]
  #打開文件，并將關(guān)鍵詞存儲(chǔ)為列表
  with open(file,'r',encoding='utf-8') as fp:
   word_list=fp.read().split(" ")
  #建立倒排索引，如果單詞不在單詞字典中，就存儲(chǔ)文件的索引，否則就添加索引到索引列表后
  for word in word_list:
   if word not in word_dict:
    word_dict[word]=[index]
   else:
    word_dict[word].append(index)
 return word_dict

基本的內(nèi)容我們有了，再考慮我們的輸入，我們希望實(shí)現(xiàn)在控制臺(tái)輸入幾個(gè)單詞，找到最符合的幾個(gè)文件。我們將輸入存儲(chǔ)為單詞列表，以此判斷該單詞是否出現(xiàn)在文件中，如果出現(xiàn)了，我們將該單詞對(duì)應(yīng)的文件的索引+1，否則繼續(xù)判斷下一個(gè)單詞。之后我們得到了關(guān)于文件索引次數(shù)的字典，我們按次數(shù)從大到小排列，然后取前幾個(gè)作為我們最后的結(jié)果。當(dāng)然，我們需要的是原始的文件名，因此，我們還要將索引映射回文件名，相關(guān)代碼如下：

def get_topk(count,topk=None):
 print(count)
 file_index = []
 #如果topk超出了返回的數(shù)目，則有多少顯示多少
 if topk > len(count):
  for i in range(0,len(count)):
   file_index.append(int(count[i][0]))
  return file_index
 if len(count)<0:
  print("沒有找到相關(guān)的文件")
  return False
 else:
  for i in range(0,topk):
   file_index.append(int(count[i][0]))
 return file_index

#得到文件名
def get_files(file_index,files_dict):
 res=[]
 for i in file_index:
  res.append(files_dict[i])
 return res

主函數(shù)：

def main():
 print("請(qǐng)輸入要查找的內(nèi)容，不同單詞間','隔開：")
 words = input().split(',')
 #獲得文件名和文件名索引字典
 files_name, files_dict = file_store()
 #提取關(guān)鍵詞或分詞
 transform(files_name)
 #倒排索引建立
 word_dict = invert_index()
 count={}
 #統(tǒng)計(jì)文件索引的次數(shù)
 for word in words:
  if word in word_dict:
   for file in word_dict[word]:
    if file not in count:
     count[file]=1
    else:
     count[file]+=1
  else:
   continue
 #按次數(shù)從大到小排列
 count=sorted(count.items(),key=lambda i:i[1],reverse=True)
 #返回前k個(gè)文件索引
 file_index=get_topk(count,topk=3)
 if file_index != False:
  print("與之描述最可能的文件是：")
  #返回文件名，并輸出結(jié)果
  res=get_files(file_index,files_dict)
  print(res)

最后，我們運(yùn)行主函數(shù)：

if __name__ == '__main__':
 main()

最終結(jié)果：

我們將topk改為3：

總結(jié)

以上所述是小編給大家介紹的Python倒排索引之查找包含某主題或單詞的文件，希望對(duì)大家有所幫助，如果大家有任何疑問請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！
如果你覺得本文對(duì)你有幫助，歡迎轉(zhuǎn)載，煩請(qǐng)注明出處，謝謝！

最新評(píng)論