Make fuzzy edit distance and transpositions configurable

Đang mở
  • Có gì không ổn?
#54 0 bình luận 0 reaction 1 người được giao Xem trên GitHub

Maintainer thường phản hồi trong vòng 1 ngày

@kylebernhardy đang làm issue này rồi.

Từ ngày 30/10/2026.

Đánh giá

Độ khó
4/5
Thời gian dự kiến
3-5 ngày
Mức phù hợp với người mới
48/100
Loại issue
Tính năng
Độ rõ ràng
Đặc tả rõ ràng
Mức độ hoạt động
Sôi nổi
Công nghệ
node.js, rust, typescript
Lĩnh vực
backend, search

Hướng nghiên cứu

Start by reading ts/native.ts and src/engine.rs at the assessed revision, then trace how query options pass through the packed protocol into native queries and tracing. Use the README wrapper contract and Tantivy’s fuzzy-query capability as references. Done means bounded distance and transposition options work for fuzzy and fuzzy-prefix clauses with consistent validation, preserved defaults, the specified Unicode, ranking, Boolean, and distance tests, and expansion/latency qualification.

Do mô hình lập chỉ mục viết ra từ nội dung của issue.

Mô tả

Outcome

Make fuzzy edit distance and transpositions configurable.

Current behavior

Verified by source inspection of the public API and native implementation at the assessed revision; no runtime reproduction was performed. Native fuzzy and fuzzy-prefix queries hardcode edit distance 1 and transpositions enabled. Callers cannot request distance 2 or disable transposition matching.

Acceptance criteria

  • Expose bounded edit-distance and transposition options for fuzzy and fuzzy-prefix clauses, preserving current defaults.
  • Carry options through TypeScript, packed protocol, native queries, and tracing with consistent validation.
  • Test Unicode edits and transpositions, exact-vs-fuzzy ranking, Boolean clauses, and both supported distances.
  • Qualify expansion and latency on representative catalogs before promoting fuzzy-prefix beyond its current preview status.

References and scope

Parent: Epic: Extend fulltext search capabilities beyond the initial wrapper API.

Tantivy capability. Wrapper contract. This is proposed standalone-library capability with no committed release. Application-specific authorization, source projection, and product API integration are outside this issue.

Deferred matching-policy scope

Follow-up from Add bounded deep-result traversal and qualify autocomplete limits: continuation does not change edit distance, transpositions or ranking coefficients.

  • Qualify exact-versus-fuzzy ranking coefficients and eligibility rules before changing their defaults. Document changes as matching/ranking policy, independently of result-page capacity.
  • Measure vocabulary/postings growth and scorer-construction costs; exact-prefix expansion guards do not bound every fuzzy path.

Tantivy 0.27 reuse and query-cost follow-up

Follow-up from Upgrade fulltext to Tantivy 0.27 with safe index rebuilds; code-trace evidence against the reviewed engine, with no isolated performance measurement yet.

  • Complete native automaton reuse for full-fuzzy tracing after measuring preparation costs. Fuzzy-prefix reuse is implemented in PR72; preserve current-source policy, UTF-16 spans, truncation and deadlines.
  • Benchmark the repeated exact branch used to add the exact-match bonus in fuzzy and fuzzy-prefix queries. It currently composes the same matching query as BM25 and constant-score branches. Preserve score bits and exact-versus-fuzzy ordering; avoid adding a wrapper-owned scorer unless a measured win justifies its maintenance.
  • Keep these refactors independent from changing fuzzy defaults or exposing new options. Report allocation/scorer costs separately from end-to-end latency and do not infer a speedup from fewer query objects.

Fuzzy-prefix tracing reuses native matching semantics; full-fuzzy reuse remains deferred following the measurements below. This does not expand this issue's release commitment.

Fixed fuzzy score contract

The planning review for Upgrade fulltext to Tantivy 0.27 with safe index rebuilds retained the explicit ConstScoreQuery layer. Although the pinned fuzzy scorer already returns a constant, removing that layer would make the wrapper's ranking contract depend on an upstream implementation detail.

  • If revisiting this simplification, pin the authoritative constant-score contract with regression assertions across boosts, prefix/non-prefix modes and engine upgrades. Preserve score bits and continuation ordering; compare latency before accepting additional upstream coupling.

Native matching reuse: measured safe scope

Implemented in Upgrade fulltext to Tantivy 0.27 with safe index rebuilds: lazy Tantivy automata replace the fuzzy-prefix predicate. Exact prefixes avoid DFA construction. Eligibility, UTF-16 spans, current-source matching, deadlines and constant scores retain their existing behavior. The direct exact tantivy-fst dependency already existed transitively; lockstep upgrades are documented. No global cache or public API expansion is introduced.

Full-fuzzy native reuse was implemented and measured, then reverted before pushing: sixteen inflected query terms against twenty near-length source tokens increased median p50 from 0.0554 to 0.1874ms across three paired optimized macOS arm64 runs. This exceeded the preset threshold of both 10% and 0.1ms. The original allocation-free full-fuzzy predicate remains guarded by native dictionary parity checks. The retained eight-case driver covers actual prefix edits, preparation-heavy requests and first-call metadata.

For the final prefix-only scope, the corresponding full-fuzzy control was 0.0563→0.0568ms; small prefix requests were 0.0163→0.0213ms, and sixteen-term/10,000-token prefix requests were 2.4623→1.9810ms. These synthetic local measurements do not establish production or isolated Linux improvements. Fresh platform qualification remains pending.

  • Revisit full-fuzzy native reuse only after acceptable short, many-term preparation cost is demonstrated without disproportionate caching or routing complexity.
  • Public distance/transposition options and exact-bonus scorer simplification retain the existing acceptance criteria above.

Query-control review follow-up

Keep the existing four-character fuzzy-prefix minimum and native fuzzy dictionary traversal. At distance two this can match two-character prefix roots; the 50-term exact-prefix expansion cap does not bound the fuzzy branch at either distance. A finite 32,000-term reachable-dictionary profile passed correctness, latency, memory and timeout recovery, but does not qualify arbitrary corpus breadth or Linux deployment headroom. Fuzzy-prefix remains preview. Revisit eligibility or native expansion admission only with production-oriented workload evidence; preserve requested native semantics and source-trace parity.

Review-Deferral: 01438370a04a4d63 severity=minor category=performance

Comment generated by kAIle (GPT-6)

Ngôn ngữ chính
Rust
Star
3
Fork
0
Merge trung bình
15 giờ 12 phút
Pull request đã merge (30 ngày)
11

Chuẩn bị môi trường

Bắt đầu từ đâu

  1. Đọc hết issue, rồi đọc hướng dẫn đóng góp của dự án.
  2. Bình luận trên issue rằng bạn sẽ nhận — tránh hai người làm cùng một việc.
  3. Fork repository và làm thay đổi trên một nhánh.
  4. Mở pull request có tham chiếu số hiệu của issue.

Issue khác của HarperFast/fulltext

Tất cả issue của HarperFast/fulltext

Issue tương tự

Thêm issue về Rust

Nhận issue mới trong hộp thư của bạn

Bản tóm tắt ngắn những issue GitHub phù hợp với người mới.