iOS에서 전체 텍스트 하위 문자열 검색

Question

iPhone/iPad 앱을 사용하면 레코드에 포함 된 하위 문자열에 대해 약 10,000 개의 레코드 (각 단락의 텍스트 정보)를 신속하게 검색 할 수 있습니다. 따라서 레코드에 "Flame"이라는 단어가 포함되어 있으면 "lame"에 대한 쿼리가 일치해야합니다.

현재 SQLite를 사용하고 있지만 "%% LIKE % 검색"은이 많은 레코드에 비해 너무 느립니다. SQLite는 접두사 와일드 카드 만 지원하므로 (예 : "* lame"이 아닌 "Flam *") 전체 텍스트 검색을 사용 설정하면 내 필요를 완전히 충족시키지 못하는 것 같습니다.

거대한 크기의 텍스트 (~ 350K)를 사용하고 Boyer-Moore 알고리즘을 사용한다고 [NSString rangeOfString : ...]하고 실험했습니다. 이것은 "LIKE % term %"검색보다 빠르지 만, 내가 바라는 종류의 속도는 아닙니다.

이러한 종류의 확장 가능한 하위 문자열 검색을 달성하고 iPhone에서 작동 할 수있는 방법이나 라이브러리에 대한 제안 사항이 있으십니까?

Answer 1

여기에는 여러 가지 옵션이 있습니다. 나는 각각의 bechmarks에 대해 알지 못하기 때문에 몇 가지 테스트를해야 할 것입니다.

첫 번째는 SQLite의 FTS3 확장입니다. 이 http://regularrateandrhythm.com/regular-rate-rhythm-blog/sqlite3-fts-in-IOS4.html

그런 방법 아이폰 OS 4에 도입 된 정규 표현식에 대해 : 전 아이폰 OS 4
http://developer.apple.com/library/ios/#documentation/Foundation/Reference/NSRegularExpression_Class/Reference/Reference.html

, 당신은 RegexKitLite를 사용할 수 있습니다 이렇게하면 빠르고 색인 전체 텍스트 검색을 제공해야
http://regexkit.sourceforge.net/RegexKitLite/index.html

정규 표현식을 사용하기로 결정한다면, 그 최적화하는 방법에이 항목을 살펴 걸릴 :
How to speed up iPhone regular expressions with NSRegularExpression?

을

Answer 2

아마도 두 번째 접근 방식을 비동기식 접근 방식과 결합하는 것이 좋습니다. 텍스트의 큰 블록을 5,10으로 나누고 같은 크기의 스레드로 개별적으로 검색하십시오. 그런 다음 일치 항목을 올바르게 배치하는 방법을 알고있는 좌표 시스템을 사용하여 결과를 결합합니다 (예 : 스레드 5에서 검색된 영역 5 및 문서 x, 위치 y와 관련되는 위치 337에서 일치를 찾음). 더 많은 스레드를 추가하는 것이 좋지 않은 경우 한계가 있다는 것을 알게 될 것입니다. 그렇게되면 알아낼 첫 번째 것이 될 것입니다.

Answer 3

텍스트를 토큰 화 (단어로 분할) 할 수없는 경우 색인을 생성 할 수 없습니다. LIKE가 순차 검색 인 이유입니다. 하위 문자열이 어떻게 든 제한 될 수 없다면 (예를 들어 항상 하위 문자열의 첫 번째 문자 또는 고정 길이를 드롭하면) 텍스트를 가능한 모든 토큰 목록으로 저장할 수 없으며 해당 토큰을 인덱싱 할 수 없습니다. 열쇠 (말장난)는 색인을 생성하는 비용이 선형 검색의 비용보다 적은 토큰 목록을 생성하는 알고리즘을 찾는 것입니다.