Thuật toán tìm kiếm mờ của 'text to' của textmate là gì?

Question

Tìm kiếm mờ 'đi tới tập tin' của Textmate thực sự tuyệt vời.

Trình cắm thêm Command-T của Wincent cho vim thực hiện điều gì đó tương tự và nó cũng xuất hiện.

Ai đó có thể giải thích cách hoạt động của các công việc này? Có một thuật ngữ chung cho phương pháp họ sử dụng?

Edit: tôi chi tiết ít hơn về những gì các công cụ làm

Các công cụ cho phép bạn thu hẹp một danh sách tùy chọn (trong hồ sơ vụ án này đường dẫn) khi bạn gõ.

Ví dụ nếu tôi có các tập tin sau đây:

/app/models/people.rb 
/app/models/address.rb 
/app/person.rb 
/person.rb 

để có được để thu hẹp danh sách để /app/models/people.rb tôi có thể gõ bất cứ điều nào sau đây:

amp 
peo 
mp 
modelsp 

nó rất linh hoạt và tôi tìm thấy tôi tự bỏ lỡ 'danh sách thu hẹp' này khi ứng dụng tôi đang sử dụng không có. Tôi muốn tìm hiểu thêm về nó để tôi có thể thực hiện các plugin của riêng mình nếu tôi cảm thấy cần thiết. Ước gì có thể giải thích nó tốt hơn, nhưng đó là lý do tại sao tôi ở đây :)

Để nhìn thấy nó trong hành động hãy nhìn vào Wincent của demo of command-t

Answer 1

Dường như đang thực hiện tìm kiếm ký tự đại diện giữa mỗi chữ cái.

amp -> *a*m*p* 
peo -> *p*e*o* 
mp -> *m*p* 
modelsp -> ... 

Nếu chỉ khớp một mục trong danh sách tùy chọn, thì nó sẽ trả về mục đó là tùy chọn dự định.

Answer 2

Dường như Command-T hiện một loại dựa trên điểm double cho bằng chức năng recursive_match trong match.c để thực hiện tìm kiếm mờ. Nguồn của Command-T có bản quyền của tác giả nhưng nguồn có thể được tìm thấy bằng cách mở vimball trong trình soạn thảo văn bản (tải xuống ở dưới cùng của this page) và có thể được sử dụng làm nguồn cảm hứng cho thuật toán tìm kiếm mờ chung hơn (bởi ai đó) đọc C tốt hơn tôi ít nhất).

Answer 3

Không có ý tưởng về cách thức này hoạt động, nhưng để tra cứu nhanh, bạn có thể tạo một cái gì đó tương tự như http://en.wikipedia.org/wiki/Directed_acyclic_word_graph và có độ phức tạp O (L), trong đó L là độ dài của mẫu tìm kiếm.

Answer 4

Làm phụ trang: Hãy xem (Apache Solr) và cách tạo chỉ mục. Tôi thấy mình sử dụng nó một chút khi tôi đang cố gắng thực hiện một cái gì đó tương tự như Command-T của Textmate trên web.

Kiểm tra cụ thể EdgeNGramFilterFactory. Tôi tin rằng thậm chí có thể có một số sourcecode một nơi nào đó. (Đó là trong Java mặc dù ...)

Answer 5

Hình như đây là mã chính xác mà bạn đang nói về:

https://github.com/textmate/textmate/blob/master/Frameworks/text/src/ranker.cc