Cách tốt nhất để triển khai tìm kiếm chuỗi con trong SQL là gì?

Xem bản trình bày của tôi Tìm kiếm toàn văn bản thực tế trong MySQL .

Tôi đã so sánh:

LIKE vị ngữ
Biểu thức chính quy vị ngữ (không tốt hơn LIKE )
MyISAM FULLTEXT lập chỉ mục
Tìm kiếm Nhân sư
Apache Lucene
Lập chỉ mục ngược
Google Công cụ Tìm kiếm Tuỳ chỉnh

Hôm nay những gì tôi sẽ sử dụng là Apache Solr , đưa Lucene trở thành một dịch vụ với nhiều tính năng và công cụ bổ sung.

Lại nhận xét của bạn:Aha, được rồi, không. Không có khả năng tìm kiếm toàn văn bản nào mà tôi đã đề cập sẽ giúp ích được, vì tất cả chúng đều giả định một số loại ranh giới từ

Một cách khác để tìm các chuỗi con tùy ý một cách hiệu quả là N-gram cách tiếp cận. Về cơ bản, hãy tạo một chỉ mục của tất cả các chuỗi N chữ cái có thể có và trỏ đến các chuỗi mà mỗi chuỗi tương ứng xảy ra. Thông thường, điều này được thực hiện với N =3 hoặc bát quái , bởi vì đó là điểm thỏa hiệp giữa việc so khớp các chuỗi con dài hơn và giữ chỉ mục ở kích thước có thể quản lý được.

Tôi không biết bất kỳ cơ sở dữ liệu SQL nào hỗ trợ lập chỉ mục N-gram một cách minh bạch, nhưng bạn có thể tự thiết lập nó bằng cách sử dụng chỉ mục đảo ngược :

create table trigrams (
  trigram char(3) primary key
);

create table trigram_matches (
  trigram char(3),
  document_id int,
  primary key (trigram, document_id),
  foreign key (trigram) references trigrams(trigram),
  foreign key (document_id) references mytable(document_id)
);

Bây giờ điền nó một cách khó khăn:

insert into trigram_matches
  select t.trigram, d.document_id
  from trigrams t join mytable d
    on d.textcolumn like concat('%', t.trigram, '%');

Tất nhiên điều này sẽ mất khá nhiều thời gian! Nhưng sau khi hoàn tất, bạn có thể tìm kiếm nhanh hơn nhiều:

select d.*
from mytable d join trigram_matches t
  on t.document_id = d.document_id
where t.trigram = 'abc'

Tất nhiên, bạn có thể tìm kiếm các mẫu dài hơn ba ký tự, nhưng chỉ mục đảo ngược vẫn giúp thu hẹp tìm kiếm của bạn rất nhiều:

select d.*
from mytable d join trigram_matches t
  on t.document_id = d.document_id
where t.trigram = 'abc'
  and d.textcolumn like '%abcdef%';