Nếu bạn chỉ bị ràng buộc với MySQL thì không có một giải pháp dễ dàng.
Thông thường điều này được giải quyết bằng cách sử dụng lập chỉ mục ngram chuyên biệt để lọc tìm kiếm ứng viên nhanh chóng và sau đó chỉ tính toán levensthein trên 10-50 ứng viên, nhanh hơn so với việc tính toán levensthein cho tất cả các cặp.
Các công cụ tìm kiếm văn bản đầy đủ chuyên dụng như Solr / Lucene tích hợp sẵn tính năng này.
PostgreSQL có mô-đun đóng góp pg_trgm (http://www.postgresql.org/docs/9.0/static/pgtrgm.html) hoạt động giống như một sự quyến rũ.
Bạn thậm chí có thể mô phỏng điều này trong MySQL bằng cách sử dụng lập chỉ mục toàn văn bản, nhưng bạn phải thu thập các từ từ tất cả các tài liệu của mình để chuyển đổi chúng sang ngrams, tạo chỉ mục văn bản đầy đủ trên chúng và hack tất cả chúng lại với nhau để tra cứu nhanh chóng. Điều này mang đến đủ loại rắc rối với việc dự phòng, đồng bộ hóa ... không đáng để bạn mất thời gian.