Mục tiêu-c: Fast Fuzzy Search Match

Question

Có ai biết thực hiện nhanh việc tìm kiếm mờ phù hợp với Mục tiêu-c không? (Thuật toán levenshtein-distance).

Tôi tìm thấy điều này: https://github.com/thetron/StringScore/blob/master/NSString%2BScore.m - nhưng tiếc là khá chậm. Tôi cần so sánh điều này với khoảng 200 chuỗi và liên tục - mỗi lần gõ phím mới.

Bất kỳ ý tưởng nào?

Answer 1

Nếu NSString + Điểm làm những gì bạn muốn nhưng là quá chậm, bạn có thể bắt đầu bằng cách tăng tốc nó lên. Các dòng 23 đến 28 trong -scoreAgainst:fuzziness:options: là mã thiết lập chỉ cần thực hiện một lần, không phải trên mỗi 200 lần so sánh. Vì vậy, kéo mã đó ra thành một phương pháp thiết lập và đo lại.

Edit:

Là một tập thể dục, tôi forked StringScore, chiết xuất mã thiết lập và đã làm thay đổi tối thiểu để có được một số cải tiến hiệu suất, sau đó đo nó. Tôi đã sử dụng 1000 từ ngẫu nhiên, nhóm chúng thành ba từ (ví dụ: "uống chấm bị gián đoạn"). Đối với mỗi nhóm, tôi đã thực hiện thiết lập (như đã nói trong câu trả lời gốc này) và sau đó so sánh chuỗi với tất cả 1000 nhóm. Điều này mất khoảng 11 giây trên Core 2 Duo của tôi.

Vì vậy, so sánh một từ với 1000 mất khoảng 11 ms. Bây giờ bạn chỉ cần 1 đến 200, vì vậy nó sẽ có lẽ cũng dưới 10 ms. Điều đó sẽ làm việc cho bạn?

(Nhân tiện, gần một nửa thời gian vẫn được dùng trong rangeOfString: tìm một ký tự đơn; điều này có thể thực hiện nhanh hơn nhiều, nhưng tôi không muốn nhận được chi tiết thuật toán.)

Answer 2

Tôi không biết về các thuật toán bạn đang đề cập thực hiện trong Objective-C

Có một lý do bạn không sử dụng được xây dựng trong chức năng của NSPredicate với CoreData. Tôi đã tìm thấy điều này rất nhanh chóng tìm kiếm hơn 200 chuỗi.

Ví dụ, đưa ra một NSString * searchText và fetchedResultsController

NSPredicate * predicate = [NSPredicate predicateWithFormat:@"name CONTAINS[cd] %@", searchText]; 

self.filteredListContents = [[[self fetchedResultsController] fetchedObjects] filteredArrayUsingPredicate:predicate]; 

Bạn cũng có thể sử dụng một NSPredicate trên một NSArray, mà tôi giả sử bạn đã cố gắng và tìm thấy là quá chậm.

Từ các tài liệu táo

NSMutableArray *array = 
[NSMutableArray arrayWithObjects:@"Nick", @"Ben", @"Adam", @"Melissa", nil]; 

NSPredicate *bPredicate = [NSPredicate predicateWithFormat:@"SELF beginswith[c] 'a'"]; 

NSArray *beginWithB = [array filteredArrayUsingPredicate:bPredicate]; 
// beginWithB contains { @"Adam" }. 

NSPredicate *sPredicate = [NSPredicate predicateWithFormat:@"SELF contains[c] 'e'"]; 

[array filterUsingPredicate:sPredicate]; 
// array now contains { @"Nick", @"Ben", @"Melissa" } 

https://developer.apple.com/library/mac/#documentation/Cocoa/Conceptual/Predicates/Articles/pSyntax.html