Babelia ou comment j'apercoie un moteur de recherche

Python Projets
1

J’ai tapé du code et ça ressemble a un moteur de recherche.

Je vais faire un passage bref sur les algorithmes que j’utilise.

Pour le moment, babelia fallback sur une recherche sur duckduckgo quand c’est pas une commande connue, voila le code:

Dans raxes.py on peux lire:

async def search(query):
    # query
    url = 'https://lite.duckduckgo.com/lite/'

    async with httpx.AsyncClient() as http:
        response = await http.post(url, data=dict(q=query))

        if response.status_code != 200:
            raise StopIteration()
        content = response.content.decode('utf8')

    # extract
    html = string2html(content)

    hits = html.xpath('//a[@class="result-link"]/@href')

    for hit in hits:
        yield hit

Note: httpx.AsyncClient() peut-être recyclé / re-use dans l’application, alors que la cela crée un client pour chaque appel, ce qui est moins performant.

Dans frontend.py on peux trouver un langage qui permet d’embarqué du HTML dans du python, sans passer par un décodeur pour implémenter un truc a la jsx, a la place ca ressemble a h.div(Class="hero")["coucou"]. La fonction serialize fonctionne de concert avec preactjs. preactjs est un clone de reactjs, qui a l’avantage d’être livré avec un seul fichier .js ie. pas besoin d’installer nodejs et webpack. Le journal The Guardian utilise preactjs pour son frontend. Le serveur va transformer la représentation sous forme d’objet python en bon vieux JSON, un petit algorithme JavaScript va prendre la main pour traduire le JSON en appel dom / virtual dom kivonbien pour preactjs (indentation approximative):

function translate(json) {
    // create callbacks
    Object.keys(json[PROPERTIES]).forEach(function(key) {
	// If the key starts with on, it must be an event handler,
	// replace the value with a callback that sends the event
	// to the backend.
	if (key.startsWith('on')) {
	    json[PROPERTIES][key] = makeEventHandlerCallback(key, json[PROPERTIES][key]);
	}
    });

    let children = json[CHILDREN].map(function(child) {
	if (child instanceof Array) {
	    // recurse
	    return translate(child);
	} else { // it's a string or a number
	    return child;
	}
    });

    return preact.h(json[TAG], json[PROPERTIES], children);
}

Les events du DOM sont forward au backend a travers une websocket, voir makeEventHandlerCallback, remarque: c’est le strict minimum que j’ai implémenté, il est souhaitable d’étendre le support des évents du DOM pour sérialiser plus finement les évents et supporter plus de cas.

Ce bout de code ne se generalise pas c’est un cas spécifique a l’implémentation de la gui de babelia, mais le reste peut se généraliser en framework dans l’esprit de phoenix :bird: liveview.

Les parties indexation et recherche sont implémentées dans pstore.py a la racine du depot, c’est un fork du pstore.py de asyncio-foundationdb qui n’utilise pas de map-reduce.

Je vous présente l’ensemble de la fonction d’indexation:

async def index(tx, store, docuid, counter):
    # translate keys that are string tokens, into uuid4 bytes with
    # store.tokens
    tokens = dict()
    for string, count in counter.items():
        query = nstore.select(tx, store.tokens, string, nstore.var('uid'))
        try:
            uid = await query.__anext__()
        except StopAsyncIteration:
            uid = uuid4()
            nstore.add(tx, store.tokens, string, uid)
        else:
            uid = uid['uid']
        tokens[uid] = count

    # store tokens to use later during search for filtering
    found.set(
        tx,
        found.pack((store.prefix_counters, docuid)),
        zstd.compress(found.pack(tuple(tokens.items())))
    )

    # store tokens keys for candidate selection
    for token in tokens:
        found.set(tx, found.pack((store.prefix_index, token, docuid)), b'')

L’algo est en deux étapes:

  1. Première étape: enregistrer le document représenter par un sac de mot (bag-of-word) appelé counter, c’est l’index avant [forward] qui associe l’identifiant docuid a son contenu le simili dico counter;
  2. Deuxième étape: créer les liens arrières [backward] aussi appelées inversés [inverted] qui associent chaque mot / clef avec le docuid et donc le sac de mots counter par jointure.

Pour la recherche:

async def search(tx, store, keywords, limit=13):
    coroutines = (_keywords_to_token(tx, store.tokens, keyword) for keyword in keywords)
    keywords = await asyncio.gather(*coroutines)
    # If a keyword is not present in store.tokens, then there is no
    # document associated with it, hence there is no document that
    # match that keyword, hence no document that has all the requested
    # keywords. Return an empty counter.
    if any(keyword is None for keyword in keywords):
        return list()

    # Select seed token
    coroutines = (_token_to_size(tx, store.prefix_index, token) for token in keywords)
    sizes = await asyncio.gather(*coroutines)
    _, seed = min(zip(sizes, keywords), key=itemgetter(0))

    # Select candidates
    candidates = []
    key = found.pack((store.prefix_index, seed))
    query = found.query(tx, key, found.next_prefix(key))

    async for key, _ in query:
        _, _, uid = found.unpack(key)
        candidates.append(uid)

    # XXX: 500 was empirically discovered, to make it so that the
    #      search takes less than 1 second or so.
    if len(candidates) > 500:
        candidates = random.sample(candidates, 500)

    # score, filter and construct hits aka. massage
    hits = Counter()

    coroutines = (massage(tx, store, c, keywords, hits) for c in candidates)
    await asyncio.gather(*coroutines)

    out = hits.most_common(limit)

    return out

L’algorithme va sélectionner dans la requête de l’utilisateur représenté par keywords le mot le moins fréquent, ça élague en une short liste qu’y s’appelle candidates. J’ai hard code un sampling a 500 items que j’ai déterminé empiriquement mais qui idéalement ne devrait pas exister, ou au moins devrait se configurer au démarrage de l’application en faisant un benchmark. Les candidates sont ensuite masser, en fait il s’agit de calculer le score de tous les documents candidats issues de l’étape précédente:

async def massage(tx, store, candidate, keywords, hits):
    score = 0
    counter = await found.get(tx, found.pack((store.prefix_counters, candidate)))
    counter = dict(found.unpack(zstd.decompress(counter)))
    for keyword in keywords:
        try:
            count = counter[keyword]
        except KeyError:
            return None
        else:
            score += count
    hits[candidate] = score

Si vous changez le code pour ne pas utiliser gather c’est BEAUCOUP plus lent.

Vous trouverez aussi different programme pour aspirer wikipedia, hackernews, …:

https://git.sr.ht/~amirouche/python-babelia/tree

Bonne lecture !

ref: sudopython - moteur de recherche textuel
ref: Viabilite d'un moteur de recherche pour le (python) francophone

1 « J'aime »
2

Edit: Le pstore.py de babelia.one fait une sorte de map-reduce, mais sans mobiliser un CPU par document ou groupe de document (contrairement ce que je fais avec Jack). Au lieu d’utiliser des process POSIX ou des threads POSIX. J’utilise les coroutines Python. Les coroutines peuvent occuper leur CPU un certains temps, cela dépend de la taille des documents [wanna be capsule].

En supportant une étape de scoring dite out-of-core, on peut augmenter la valeur de sampling que j’ai écrit 500.

4

salut @amirouche , j’ai trouvé ça, ça peut t’intéresser peut-être : A look at search engines with their own indexes - Seirdy

1 « J'aime »