Hacktoberfest 2026: le issue che i maintainer hanno segnato per ottobre, aperte e adatte ai principianti. Sfoglia le issue Hacktoberfest

Bigram tokenization for CJK BM25: per-character tokens fix recall but cost precision

Aperta
  • Qualcosa non va?
#12,867 5 commenti 0 reazioni 0 assegnatari Vedi su GitHub

I maintainer di solito rispondono entro 1 giorno

Nessuno ha ancora preso questa issue.

Valutazione

Difficoltà
4/5
Tempo stimato
3-5 giorni
Idoneità per principianti
45/100
Tipo di issue
Funzionalità
Chiarezza
Specificata chiaramente
Stato di attività
Attiva
Stack tecnologico
python
Ambito
search

Direzione di ricerca

The issue discusses modifying the BM25 tokenizer in haystack/components/retrievers/in_memory.py and haystack/document_stores/in_memory.py to handle CJK text with bigrams. Start by examining the _tokenize_bm25 method and the bm25_tokenization_regex parameter. The benchmark script in the issue body provides a concrete implementation to test. 'Done' means implementing a configurable tokenization mode (unigram, bigram, or both) that passes the provided tests and maintains serialization compatibility.

Scritto dal modello di indicizzazione a partire dal testo della issue.

Descrizione

P1

Follow-up to #12836 and #12837, opened at @sjrl's request so the design can be discussed before a PR.

The problem

#12837 makes the default BM25 tokenizer split CJK text one character per token. That fixes the recall failure from #12836, but single-character tokens carry very little meaning in Korean, and the ranking suffers. Querying 서울 (Seoul) against a corpus where five of six documents are unrelated:

1. [wrong]  1.250  서점 앞에서 울고 있는 아이를 보았다.   ("a child crying in front of a bookstore")
2. [right]  1.106  서울은 대한민국의 수도이며 인구가 가장 많다.
3. [wrong]  1.053  울타리 너머로 개가 짖고 있었다.        ("a dog barking beyond the fence")

The unrelated document wins because it happens to contain 서 (from 서점, "bookstore") and 울 (from 울고, "crying"). A Hangul syllable is closer to an English letter than to a word: 서 on its own can be 書 / 西 / 序, and 울 can be the verb stem "cry" or part of 울타리 ("fence"). This is why Lucene's CJK analyzer emits bigrams rather than unigrams.

Measurements

haystack-ai==3.1.1, same corpus and same code path, swapping only the tokenizer. Script at the bottom.

tokenizer recall@10 top-1 correct 서울 precision 1-syllable query 산 tokens per KO sentence
current default 0/10 0/10 no results 0 hits 6
#12837 (unigram) 10/10 10/10 wrong doc at rank 1 3 hits 19
bigram 10/10 10/10 correct at rank 1 0 hits 13
unigram + bigram 10/10 10/10 correct at rank 1 3 hits 32

Pure bigrams recover the precision but lose single-character queries, which is what Lucene's outputUnigrams option exists for. Emitting both fixes that at the cost of token count.

Scope caveat: every number here is Korean. I have not measured Japanese or Chinese, where the same change would apply and where the tradeoffs may land differently.

What would need to change

self.tokenizer = re.compile(bm25_tokenization_regex).findall, and overlapping bigrams cannot be expressed that way. They need a lookahead capture, and then findall returns groups, so the Latin branch collapses to '' (with one group) or the result becomes tuples (with two):

re.compile(r"[^\W<CJK>]+|(?=([<CJK>]{2}))").findall("서울은 Luna 2026")
# ['서울', '울은', '', '']            <- Latin tokens lost
re.compile(r"([^\W<CJK>]+)|(?=([<CJK>]{2}))").findall("서울은 Luna 2026")
# [('', '서울'), ('', '울은'), ('Luna', ''), ('2026', '')]

Two ways out:

A. A callable tokenizer parameter. serialize_callable / deserialize_callable means it survives to_dict / from_dict by import path, so pipeline YAML still round-trips — but only for module-level functions; a lambda or a closure silently breaks that. Most flexible, largest surface.

B. A serializable mode. Something like bm25_cjk_tokenization: Literal["unigram", "bigram", "bigram_and_unigram"], with a shipped tokenizer per mode. It round-trips as a plain string with no callable-serialization caveats, at the cost of not being extensible by users.

I lean towards B for the default path, with A as a possible later addition: what most users need is a good default rather than an arbitrary tokenizer.

Open questions

  1. Which default? Unigram as #12837 ships it, with bigram opt-in, or bigram-and-unigram as the default once it has been measured on Japanese and Chinese too?
  2. Is the token count of bigram_and_unigram (roughly 5x the current default for Korean) acceptable for an in-memory store, or does that argue for pure bigrams plus a documented caveat about single-character queries?
  3. Should the benchmark live as a test, so that a future tokenizer change has to state its effect on recall and precision rather than being judged by eye?

Happy to implement whichever direction you prefer, and to contribute the benchmark as a test either way.

Benchmark script 
r"""Tokenizer comparison for haystack PR #12837 (haystack-ai==3.1.1).

Swaps only the BM25 tokenizer, holding corpus, retriever and BM25 algorithm fixed:

  current  the released default,  r"(?u)\b\w+\b"
  unigram  this PR: one token per Hangul syllable / CJK ideograph / kana
  bigram   Lucene CJKBigramFilter style: overlapping 2-grams over CJK runs
  both     bigram + unigram, i.e. Lucene's outputUnigrams=true
"""

import re

from haystack import Document
from haystack.components.retrievers.in_memory import InMemoryBM25Retriever
from haystack.document_stores.in_memory import InMemoryDocumentStore

CJK = r"ᄀ-ᇿ㄰-㆏가-힯぀-ヿ一-鿿"
CURRENT = r"(?u)\b\w+\b"
UNIGRAM = rf"[^\W{CJK}]+|[{CJK}]"
SPLIT = re.compile(rf"[^\W{CJK}]+|[{CJK}]+")
CJK_RUN = re.compile(rf"[{CJK}]+")


def cjk_tokenizer(*, bigrams: bool, unigrams: bool):
    def tokenize(text: str) -> list[str]:
        out: list[str] = []
        for m in SPLIT.finditer(text):
            s = m.group(0)
            if not CJK_RUN.fullmatch(s):
                out.append(s)
                continue
            if bigrams:
                out.extend([s[i : i + 2] for i in range(len(s) - 1)] or [s])
            if unigrams:
                out.extend(list(s))
        return out

    return tokenize


def make_store(mode: str, docs: list[Document]) -> InMemoryDocumentStore:
    regex = CURRENT if mode == "current" else UNIGRAM
    store = InMemoryDocumentStore(bm25_tokenization_regex=regex)
    if mode == "bigram":
        store.tokenizer = cjk_tokenizer(bigrams=True, unigrams=False)
    elif mode == "both":
        store.tokenizer = cjk_tokenizer(bigrams=True, unigrams=True)
    store.write_documents(docs)
    return store


def search(store: InMemoryDocumentStore, query: str, top_k: int = 10) -> list[Document]:
    return InMemoryBM25Retriever(store, top_k=top_k, scale_score=False).run(query=query)["documents"]


# One natural sentence per city, mentioning it once with an attached particle.
CITIES = [
    ("서울", "서울은 대한민국의 수도이며 인구가 가장 많다."),
    ("부산", "부산은 대한민국 제2의 도시이자 최대 항구이다."),
    ("제주", "제주에는 화산 활동으로 만들어진 독특한 지형이 많다."),
    ("대구", "대구를 방문하면 근대 골목길을 걸어볼 수 있다."),
    ("인천", "인천에서 출발하는 국제선 항공편이 가장 많다."),
    ("광주", "광주의 5월은 역사적으로 중요한 의미를 가진다."),
    ("대전", "대전은 과학 연구 단지가 밀집한 도시로 알려져 있다."),
    ("울산", "울산에는 자동차와 조선 산업 단지가 모여 있다."),
    ("세종", "세종으로 여러 중앙 행정 기관이 이전하였다."),
    ("수원", "수원에는 조선 시대에 쌓은 화성이 남아 있다."),
]

# Unrelated sentences that happen to contain 서 or 울 inside other words.
DISTRACTORS = [
    "서점 앞에서 울고 있는 아이를 보았다.",
    "서류를 모두 제출해야 접수가 완료된다.",
    "울타리 너머로 개가 짖고 있었다.",
    "서열을 정하는 회의가 길어졌다.",
    "경기도는 서쪽 해안을 따라 갯벌이 넓다.",
]

SINGLE = ["산이 높고 물이 깊다.", "부산은 항구 도시이다.", "등산을 좋아한다."]

print(f"{'tokenizer':9} {'recall@10':>9} {'top-1':>7} {'서울 precision':>16} {'산 hits':>8} {'KO tokens':>10}")
for mode in ("current", "unigram", "bigram", "both"):
    store = make_store(mode, [Document(content=s, meta={"city": c}) for c, s in CITIES])
    recall = sum(1 for c, _ in CITIES if any(d.meta["city"] == c for d in search(store, c)))
    top1 = sum(1 for c, _ in CITIES if (r := search(store, c)) and r[0].meta["city"] == c)

    precision_docs = [Document(content=CITIES[0][1], meta={"relevant": True})]
    precision_docs += [Document(content=s, meta={"relevant": False}) for s in DISTRACTORS]
    ranked = search(make_store(mode, precision_docs), "서울", top_k=3)
    precision = "no results" if not ranked else ("correct@1" if ranked[0].meta["relevant"] else "WRONG@1")

    single = len(search(make_store(mode, [Document(content=s) for s in SINGLE]), "산", top_k=3))
    tokens = len(store._tokenize_bm25(CITIES[0][1]))
    print(f"{mode:9} {recall:>7}/10 {top1:>5}/10 {precision:>16} {single:>8} {tokens:>10}")

print("\nRanking for the query 서울:")
precision_docs = [Document(content=CITIES[0][1], meta={"relevant": True})]
precision_docs += [Document(content=s, meta={"relevant": False}) for s in DISTRACTORS]
for mode in ("unigram", "bigram"):
    print(f"  {mode}")
    for i, d in enumerate(search(make_store(mode, precision_docs), "서울", top_k=3)):
        print(f"    {i + 1}. [{'right' if d.meta['relevant'] else 'wrong'}] {d.score:6.3f}  {d.content}")

print("\nAverage document length, 20 Korean + 3 English documents:")
ko = [f"서울은 대한민국의 수도이며 인구가 가장 많다. 사례 {i}." for i in range(20)]
en = [
    "Seoul is the capital of South Korea and has the largest population.",
    "Busan is the second largest city in South Korea.",
    "The capital city hosts the national government.",
]
for mode in ("current", "unigram"):
    store = make_store(mode, [Document(content=c) for c in ko + en])
    avgdl = sum(len(store._tokenize_bm25(c)) for c in ko + en) / len(ko + en)
    scores = ", ".join(f"{d.score:.3f}" for d in search(store, "capital", top_k=3))
    print(f"  {mode:9} avgdl={avgdl:5.1f}  scores for the English query 'capital': {scores}")
Lingua principale
Python
Stelle
26.6k
Fork
3.2k
Merge medio
1g 13h
PR unite (30g)
241

Preparare l'ambiente

Come iniziare

  1. Leggi tutta la issue e poi la guida ai contributi del progetto.
  2. Commenta sulla issue per dire che te ne occupi tu — evita che due persone facciano lo stesso lavoro.
  3. Fai un fork del repository e lavora su un branch.
  4. Apri una pull request che faccia riferimento al numero della issue.

Altre issue di deepset-ai/haystack

Tutte le issue di deepset-ai/haystack

Issue simili

Altre issue su Python

Ricevi le nuove issue nella tua casella

Un breve riepilogo di issue GitHub adatte ai principianti.