J'ai créé un moteur de recherche qui m'intéressait depuis longtemps comme travail pour les vacances d'hiver. (Bien que ce soit foiré ...)

Environnement de travail

Puisque la requête de recherche est obtenue à partir de l'entrée standard, j'écrirai l'environnement pour le moment. L'environnement est le suivant. Mac OSX 10.9.5 Core i7(64bit) Python 2.7.9

Matériel de référence

[Introduction à la technologie de service à grande échelle [pour les développeurs Web]](http://www.amazon.co.jp/gp/product/4774143073/ref=as_li_qf_sp_asin_tl?ie=UTF8&camp=247&creative=1211&creativeASIN=4774143073&linkCode=as2&tag= shimashimao06-22)

Non seulement l'algorithme de recherche, mais aussi la mémoire et le disque sont largement décrits. En outre, c'était un livre intéressant comme matériel de lecture, car il contient également des exemples d'échecs basés sur l'expérience réelle.

Ce que j'ai fait

Il existe trois fonctions principales: la compression des données, la création d'index de translocation et la recherche.

Création de code pour la compression de données

Cette fois, nous compressons avec VBcode. Il semble qu'il existe diverses autres méthodes de compression telles que les codes PForDelta et Golomb. La raison de la compression des données est en premier lieu d'augmenter le débit global maintenant que le stockage de grande capacité peut être acheté à bas prix.

D'après le livre ci-dessus

Du point de vue du débit, il existe de nombreuses situations où il est plus rapide de compresser les données à traiter. L'ordinateur dispose de deux types de charges, CPU et E / S. En attendant qu'une E / S effectue un certain processus, la CPU ne peut pas être utilisée pour ce processus. La compression du fichier met à rude épreuve le processeur, mais elle peut réduire l'attente d'E / S. Étant donné que le processeur est souvent libre et que les E / S sont occupées, réduire la charge des E / S par compression et laisser le processeur prendre le relais augmentera le débit global.

Il y a une explication. De plus, comme celui compressé doit être décompressé, envisagez de l'utiliser lorsque le mérite de la partie E / S est supérieur à la charge appliquée à la compression / décompression, ou utilisez une méthode de compression qui a le mérite. Je pense que c'est nécessaire.

En ce qui concerne la méthode de compression, VBcode compresse en supprimant les octets redondants et en décrivant les informations avec le nombre minimum d'octets. Par exemple, l'entier 5 est 00000000 00000000 00000000 00000101 en code binaire de longueur fixe, mais peut être exprimé comme 10000101 en VBcode. Puisque 8 bits sont un bloc, il est important de faire bon usage de 128 (10 000 000 en binaire) dans le code.

Vous pouvez également obtenir l'effet de compression en triant les valeurs entières et en prenant l'écart entre les nombres. Cela semble être dérivé de la distribution de probabilité selon laquelle les petits nombres sont faciles à apparaître, mais les grands nombres sont difficiles à apparaître.

Créer et enregistrer des index transposés

Cette fois, j'ai créé un index de translocation à l'aide de bi-gramme. Je pense que de nombreuses personnes connaissent l'indice de translocation, je vais donc omettre l'explication. Dans la mise en œuvre ci-dessous { term: {(doc_id1, doc_id2,...): [[location_list1],[location_list2],...]} } La liste de publication comprenant l'emplacement est stockée dans le dictionnaire avec le terme comme clé. (Je pense qu'il existe une méthode plus décente, donc si vous la connaissez, faites-le moi savoir.) L'index de translocation créé (dictionnaire) a été enregistré dans un fichier avec cPickle.

Rechercher des documents

Il n'y a pas beaucoup d'explications, je vais donc les énumérer.

Entrez une requête de recherche à partir de l'entrée standard
Créer un terme avec bi-gramme à partir de la requête de recherche
Rechercher en vérifiant la continuité des termes dans chaque document par emplacement
Le titre et l'extrait du document de hit sont affichés

Des données d'utilisation

Veuillez télécharger à partir de la Page de support technique de l'entreprise. Nous utiliserons un fichier appelé 10000entries.txt qui contient des données de titre et un dossier appelé textes contenant des fichiers de document séparés par document_id. La capacité est de 1,4 M pour le fichier titre et de 321 Ko pour le dossier textes dans son ensemble.

Code de référence

Désolé pour le code assez sale, mais je vais le coller ci-dessous.

Tout d'abord, le code qui compresse / décompresse avec VBcode.

`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 #Déclarez la fin de la chaîne de bits(Utilisez le premier bit comme masque)
    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)

Vient ensuite la création et le stockage de l'indice de translocation.

`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)

Enfin, le code de la partie recherche.

`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_Obtenez l'ensemble des identifiants du produit
        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_Obtenez la liste d'index des identifiants
            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 ]
            #Obtenez l'emplacement de chaque document dans chaque requête
            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"

La création d'un index transposé prend énormément de temps. Cette fois, c'était bien car il y avait suffisamment de données pour tenir dans la mémoire, mais si cela ne rentre pas dans la mémoire, j'imagine que je vais fusionner l'index mis en mémoire tampon dans la base de données tout en le stockant dans la base de données et le stocker. J'étais en train de le faire. Bien que ce soit une base de données, je pense que MongoDB est facile si vous le créez avec un type de dictionnaire python.

commentaire

Je pense que c'est une spécialité profonde telle que la compression de données et la technologie de recherche, mais c'était plus facile que je ne l'avais imaginé à l'origine de simplement le créer sans y penser. Je voudrais relever le défi de créer des algorithmes de classement, ce que je n'ai pas commencé cette fois.

Nous vous prions de nous excuser pour la gêne occasionnée, mais nous vous serions reconnaissants de bien vouloir signaler toute erreur.

Les moteurs de recherche fonctionnent avec python