Suchmaschinen arbeiten mit Python
Ich habe eine Suchmaschine gemacht, an der ich mich lange als Arbeit für Winterferien interessiert habe. (Obwohl es durcheinander ist ...)
Arbeitsumgebung
Da die Suchabfrage von der Standardeingabe erhalten wird, werde ich die Umgebung vorerst schreiben. Die Umgebung ist wie folgt. Mac OSX 10.9.5 Core i7(64bit) Python 2.7.9
Referenzmaterial
[Einführung in die großtechnische Servicetechnologie [Für Webentwickler]](http://www.amazon.co.jp/gp/product/4774143073/ref=as_li_qf_sp_asin_tl?ie=UTF8&camp=247&creative=1211&creativeASIN=4774143073&linkCode=2 shimashimao06-22)
Nicht nur die Geschichte des Suchalgorithmus, sondern auch die Geschichte von Speicher und Festplatte wird ausführlich beschrieben. Darüber hinaus war es ein interessantes Buch als Lesematerial, da es auch Beispiele für Fehler enthält, die auf tatsächlichen Erfahrungen beruhen.
Was ich getan habe
Es gibt drei Hauptfunktionen: Datenkomprimierung, Erstellung des Translokationsindex und Suche.
Code für die Datenkomprimierung erstellen
Dieses Mal komprimieren wir mit VBcode. Es scheint, dass es verschiedene andere Komprimierungsmethoden wie PForDelta- und Golomb-Codes gibt. Der Grund für die Datenkomprimierung besteht in erster Linie darin, den Gesamtdurchsatz zu erhöhen, da Speicher mit großer Kapazität jetzt zu einem niedrigen Preis erworben werden können.
Nach dem obigen Buch
Unter dem Gesichtspunkt des Durchsatzes gibt es viele Situationen, in denen es schneller ist, die zu verarbeitenden Daten zu komprimieren. Der Computer verfügt über zwei Arten von Lasten: CPU und E / A. Während Sie darauf warten, dass eine E / A einen bestimmten Prozess ausführt, kann die CPU nicht für diesen Prozess verwendet werden. Das Komprimieren der Datei belastet die CPU, kann jedoch die E / A-Wartezeit verringern. Da die CPU häufig frei ist und die E / A ausgelastet ist, wird der Gesamtdurchsatz erhöht, indem die E / A-Last durch Komprimierung verringert und die CPU übernommen wird.
Es gibt eine Erklärung. Da das komprimierte Element dekomprimiert werden muss, sollten Sie es verwenden, wenn der Wert des E / A-Teils größer ist als die auf die Komprimierung / Dekomprimierung ausgeübte Last, oder eine Komprimierungsmethode verwenden, die den Vorteil hat. Ich denke es ist notwendig.
In Bezug auf die Komprimierungsmethode komprimiert VBcode, indem redundante Bytes entfernt und die Informationen mit der minimalen Anzahl von Bytes beschrieben werden. Beispielsweise ist die Ganzzahl 5 00000000 00000000 00000000 00000101 in Binärcode fester Länge, kann jedoch in VBcode als 10000101 ausgedrückt werden. Da 8 Bits ein Block sind, ist es wichtig, 128 (10000000 in Binärform) im Code gut zu verwenden.
Alternativ können Sie den Komprimierungseffekt erzielen, indem Sie die ganzzahligen Werte sortieren und die Lücke zwischen den Zahlen schließen. Dies scheint aus der Wahrscheinlichkeitsverteilung abgeleitet zu sein, dass kleine Zahlen leicht zu erscheinen sind, große Zahlen jedoch schwer zu erscheinen sind.
Erstellen und Speichern transponierter Indizes
Dieses Mal habe ich einen Translokationsindex mit Bi-Gramm erstellt. Ich denke, dass viele Leute mit dem Translokationsindex vertraut sind, deshalb werde ich die Erklärung weglassen. In der folgenden Implementierung { term: {(doc_id1, doc_id2,...): [[location_list1],[location_list2],...]} } Die Buchungsliste mit dem Speicherort wird im Wörterbuch mit dem Begriff als Schlüssel gespeichert. (Ich denke, es gibt eine anständigere Methode. Wenn Sie es wissen, lassen Sie es mich bitte wissen.) Der erstellte Translokationsindex (Wörterbuch) wurde mit cPickle in einer Datei gespeichert.
Nach Dokumenten suchen
Es gibt nicht viel Erklärung, deshalb werde ich es auflisten.
- Geben Sie eine Suchabfrage aus der Standardeingabe ein
- Erstellen Sie einen Begriff mit Bi-Gramm aus der Suchabfrage
- Suchen Sie, während Sie die Kontinuität der Begriffe in jedem Dokument nach Speicherort überprüfen
- Titel und Ausschnitt des Treffer-Dokuments werden angezeigt
Nutzungsdaten
Bitte laden Sie sie von der [Technical Review Company Support Page] herunter (http://gihyo.jp/book/2010/978-4-7741-4307-1/support). Wir werden eine Datei namens 10000entries.txt verwenden, die Titeldaten enthält, und einen Ordner namens Texte, der Dokumentdateien enthält, die durch document_id getrennt sind. Die Kapazität beträgt 1,4 MB für die Titeldatei und 321 KB für den gesamten Textordner.
Referenzcode
Entschuldigung für den ziemlich schmutzigen Code, aber ich werde ihn unten einfügen.
Zunächst der Code, der mit VBcode komprimiert / dekomprimiert wird.
vbcode.py
# coding: utf-8
from struct import pack, unpack
def vbencode_number(number):
number = int(number)
_bytes = []
while 1:
_bytes.insert(0, number % 128)
if number < 128: break
number /= 128
_bytes[-1] += 128 #Deklarieren Sie das Ende der Bitfolge(Verwenden Sie das erste Bit als Maske)
return pack('%dB' % len(_bytes), *_bytes)
def vbencode(numbers):
bytestream = ''
for number in numbers:
_bytes = vbencode_number(number)
bytestream += _bytes
return bytestream
def vbdecode(bytestream):
numbers = []
n = 0
bytestream = unpack('%dB' % len(bytestream), bytestream)
for i in xrange(len(bytestream)):
if bytestream[i] < 128:
n = 128*n + bytestream[i]
else:
n = 128*n + bytestream[i] - 128
numbers.append(n)
n = 0
return numbers
if __name__=='__main__':
numbers = (1,2,128,145)
res = vbencode(numbers)
print vbdecode(res)
Als nächstes wird der Translokationsindex erstellt und gespeichert.
index.py
# codeing: utf-8
from __future__ import unicode_literals
from collections import defaultdict
from unicodedata import normalize
import MeCab
from vbcode import vbencode
import numpy as np
import os
import cPickle
def get_title_data(input_filename):
titles = defaultdict(str)
with open(input_filename, 'r', 10000) as f:
for line in f:
try:
doc_id, cat_id, url, title = line.strip().split(b'\t')
titles[int(doc_id)] = title
except Exception, e:
doc_id, cat_id, url = line.strip().split(b'\t')
titles[int(doc_id)] = ''
return titles
def create_index(doc_base_path,titles):
main_index = defaultdict(dict)
for doc_id in titles.keys():
try:
main_index = get_index_dic(doc_base_path, doc_id, main_index)
except Exception, e:
import traceback
print traceback.format_exc()
print e
compressed_main_index = compress_postinglist(main_index)
save_index(compressed_main_index)
def save_index(index):
with open('index_bigram.pkl','w') as f:
cPickle.dump(index, f)
def compress_postinglist(index):
for key_word, posting_dic in index.items():
tup_did_location = zip( posting_dic.keys()[0],posting_dic.values()[0] ) # [(),()]
tup_did_location.sort(key=lambda x:x[0]) # [(),()]
doc_id_list = []
lctn_pl = []
for doc_id, location_list in tup_did_location:
doc_id_list.append(doc_id)
lctn_pl.append( vbencode( get_differences(location_list) ) )
d_pl = get_differences(doc_id_list)
index[key_word] = { vbencode(d_pl) : lctn_pl}
return index
def get_differences(sorted_list):
if len(sorted_list)>1:
diff_list = ( np.array(sorted_list) - np.array([0]+sorted_list[:-1]) ).tolist()
else:
diff_list = sorted_list
return diff_list
def get_index_dic(doc_base_path, doc_id, main_index):
with open(doc_base_path+'/'+str(doc_id), 'r') as f:
doc = f.read().strip()
doc = normalize('NFKC',doc.decode('utf-8')).lower()
word_list, word_location = bi_gram_tokenize(doc)
for word, location in zip(word_list, word_location):
if main_index[word]:
_keys = main_index[word].keys()[0]
if doc_id in _keys:
main_index[word][_keys][-1] += [location]
else:
main_index[word][_keys].append( [location] )
main_index[word] = {_keys+(doc_id,): main_index[word].values()[0]}
else:
main_index[word][(doc_id,)] = [ [location] ]
return main_index
def mecab_tokenize(doc):
tagger = MeCab.Tagger(b'-Ochasen')
node = tagger.parseToNode(doc.encode('utf-8'))
word_list = []
while node:
ns = node.surface
word_list.append(ns)
node = node.next
return word_list
def bi_gram_tokenize(doc):
word_list = []
word_location = []
for i in xrange(len(doc)):
term = doc[i:i+2].strip()
if len(term)!=0:
#print "term:",term
word_list.append( term )
word_location.append( i )
return word_list, word_location
def main(input_filename, doc_base_path):
titles = get_title_data(input_filename)
create_index(doc_base_path,titles)
if __name__=='__main__':
ifpath = os.getcwd()+'/../works/input'
ifname = ifpath + '/10000entries.txt'
doc_base_path = ifpath + '/texts'
main(ifname, doc_base_path)
Zum Schluss der Code für den Suchteil.
search.py
# coding: utf-8
from __future__ import unicode_literals
import os
from collections import defaultdict
import sys
from vbcode import vbdecode
import cPickle as pickle
import numpy as np
from unicodedata import normalize
def get_titles(input_filename):
with open(input_filename,'r',10000) as f:
titles = defaultdict(dict)
for line in f:
try:
doc_id, cat_id, url, title = line.strip().split(b'\t')
titles[int(doc_id)] = {'title': title, 'url':url}
except Exception, e:
doc_id, cat_id, url = line.strip().split(b'\t')
titles[int(doc_id)] = {'title':'', 'url': url}
return titles
def load_index(index_filename):
with open(index_filename, 'r') as f:
index = pickle.load(f)
return index
def search(titles, index, query, text_path):
query = normalize('NFKC',query.decode('utf-8'))
for q in query.strip().split(' '):
print "search:", query
if len(q.strip())==0: continue
bi_gram_qs = get_bigram_queries(q.strip())
if not index[bi_gram_qs[0]]: continue
# doc_Holen Sie sich den Produktsatz der ID
doc_ids = set( get_decoded_data(index[bi_gram_qs[0]].keys()[0]) )
for bi_gram_q in bi_gram_qs[1:]:
doc_ids = doc_ids & set( get_decoded_data(index[bi_gram_q].keys()[0]) )
doc_ids = list(doc_ids)
if len(doc_ids)==0: continue
location_lists = []
for bi_gram_q in bi_gram_qs:
# doc_Holen Sie sich die Indexliste der ID
all_doc_ids = get_decoded_data( index[bi_gram_q].keys()[0] )
idx_list = [ all_doc_ids.index(doc_id) for doc_id in doc_ids ]
#Abrufen des Speicherorts für jedes Dokument in jeder Abfrage
location_list = [ get_decoded_data(index[bi_gram_q].values()[0][idx]) for idx in idx_list ]
location_lists.append( location_list )
doc_id_idx_idx, locations4snippet = check_sequence(location_lists)
#print "doc_id_idx_idx:", doc_id_idx_idx
#print "doc_ids:", doc_ids
squewed_doc_ids = ( doc_ids[doc_id_idx] for doc_id_idx in doc_id_idx_idx )
for doc_id, location in zip( squewed_doc_ids, locations4snippet):
print "doc_id:",doc_id
if doc_id in titles:
print titles[doc_id]['title']
if location<50:
start = 0
else:
start = location - 50
end = location + 50
with open(text_path+'/'+str(doc_id), 'r') as f:
print f.read().strip().decode('utf-8')[start:end]
def get_bigram_queries(query):
bi_gram_qs = []
for i in xrange(0, len(query), 2):
bi_gram_q = query[i:i+2].strip()
if len(bi_gram_q) ==1 and i>0:
bi_gram_q = query[i-1:i+1]
bi_gram_qs.append( bi_gram_q )
return bi_gram_qs
def get_decoded_data(encoded_data):
decoded_data = vbdecode(encoded_data)
return np.cumsum(decoded_data).tolist()
def check_sequence(location_lists):
length = len(location_lists)
doc_id_idx_idx = []
locations4snippet = []
for doc_i, location_list in enumerate(location_lists[0]):
for location in location_list:
if length==1:
return [doc_i]
elif check_next_node(1, doc_i, location, location_lists, length):
doc_id_idx_idx.append(doc_i)
locations4snippet.append(location)
else:
continue
return doc_id_idx_idx, locations4snippet
def check_next_node(i, doc_i, location, location_lists, last_node):
for next_location in location_lists[i][doc_i]:
if location < next_location <= location+2:
if i < last_node-1:
return check_next_node(i+1, doc_i, location+2, location_lists, last_node)
else:
return True
else:
return False
if __name__=='__main__':
basepath = os.getcwd()
index_filename = basepath + '/index_bigram.pkl'
file_path = basepath + '/../works/input'
ifname = file_path + '/10000entries.txt'
text_path = file_path + '/texts'
titles = get_titles(ifname)
index = load_index(index_filename)
print "get search query"
query = raw_input()
search(titles, index, query, text_path)
print "done"
Das Erstellen eines transponierten Index nimmt enorm viel Zeit in Anspruch. Diesmal war es gut, weil es genug Daten gab, um in den Speicher zu passen, aber wenn es nicht in den Speicher passt, stelle ich mir vor, dass ich den gepufferten Index in der Datenbank zusammenführen werde, während ich ihn in der Datenbank speichere und speichere. Ich habe es geschafft. Obwohl es sich um eine Datenbank handelt, ist MongoDB meiner Meinung nach einfach, wenn Sie es mit einem Python-Wörterbuchtyp erstellen.
Kommentar
Ich denke, es ist eine tiefe Spezialität wie Datenkomprimierung und Suchtechnologie, aber es war einfacher als ich es mir ursprünglich vorgestellt hatte, es einfach zu erstellen, ohne darüber nachzudenken. Ich möchte mich der Herausforderung stellen, Ranking-Algorithmen zu erstellen, mit denen ich diesmal noch nicht begonnen habe.
Wir entschuldigen uns für die Unannehmlichkeiten, würden uns aber freuen, wenn Sie auf Fehler hinweisen könnten.
Recommended Posts