什么是倒排索引？

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

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

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

test2.txt中存有：我們愛計算機視覺

正向索引：

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

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

倒排索引：

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

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

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

python.txt

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

java.txt

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

c.txt

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

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

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

#獲取當前pyhtho文件所在的目錄：當前是：C:\gongoubo\python-work\direc\files
dir_path = os.path.dirname(os.path.abspath(__file__))
print(dir_path)
#存儲txt文件的絕對路徑為列表，同時為每個文件建立索引
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

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

#讀取每個txt文件
def transform(files_name):
    #注意打開的時候需要申明為utf-8編碼
    for i,j in enumerate(files_name):
        #打開文件
        tmp = open(j,'r',encoding='utf-8').read()
        #提取關(guān)鍵詞
        content = analyse.extract_tags(tmp)
　　　　 #也可以進行分詞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)
        #為存儲關(guān)鍵詞的txt取名，對應(yīng)這每個文件的索引
        fp=open(path+'\\'+str(i)+'.txt','w',encoding='utf-8')
        #將關(guān)鍵詞寫入到txt中
        fp.write(" ".join(content))
        fp.close()

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

 接下來，進行倒排索引的構(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)鍵詞存儲為列表
  with open(file,'r',encoding='utf-8') as fp:
   word_list=fp.read().split(" ")
  #建立倒排索引，如果單詞不在單詞字典中，就存儲文件的索引，否則就添加索引到索引列表后
  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)容我們有了，再考慮我們的輸入，我們希望實現(xiàn)在控制臺輸入幾個單詞，找到最符合的幾個文件。我們將輸入存儲為單詞列表，以此判斷該單詞是否出現(xiàn)在文件中，如果出現(xiàn)了，我們將該單詞對應(yīng)的文件的索引+1，否則繼續(xù)判斷下一個單詞。之后我們得到了關(guān)于文件索引次數(shù)的字典，我們按次數(shù)從大到小排列，然后取前幾個作為我們最后的結(jié)果。當然，我們需要的是原始的文件名，因此，我們還要將索引映射回文件名，相關(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("請輸入要查找的內(nèi)容，不同單詞間','隔開：")
 words = input().split(',')
 #獲得文件名和文件名索引字典
 files_name, files_dict = file_store()
 #提取關(guān)鍵詞或分詞
 transform(files_name)
 #倒排索引建立
 word_dict = invert_index()
 count={}
 #統(tǒng)計文件索引的次數(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個文件索引
 file_index=get_topk(count,topk=3)
 if file_index != False:
  print("與之描述最可能的文件是：")
  #返回文件名，并輸出結(jié)果
  res=get_files(file_index,files_dict)
  print(res)

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

if __name__ == '__main__':
 main()

最終結(jié)果：

我們將topk改為3：

總結(jié)

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

最新評論