Búsqueda de subcadena de texto completo en iOS

Question

Necesito mi aplicación de iPhone/iPad para poder buscar rápidamente alrededor de 10.000 registros (aproximadamente un párrafo de texto, cada uno), para cualquier subcadena contenida dentro del registro. Entonces, si el registro contiene la palabra "Llama", la consulta de "cojo" debe coincidir.

Actualmente estoy usando SQLite, pero las búsquedas de "LIKE% term%" son demasiado lentas para estos muchos registros. Habilitar la búsqueda de texto completo no parece satisfacer completamente mis necesidades, ya que SQLite solo admite prefijos comodines (por ejemplo, "Flam *", no "* lame").

He experimentado con el uso de una burbuja de texto gigante (~ 350K), y haciendo [NSString rangeOfString: ...], que creo que utiliza un algoritmo Boyer-Moore. Esto es más rápido que las búsquedas de "LIKE% term%", pero todavía no es el tipo de velocidad que estoy esperando.

¿Alguna sugerencia de enfoques, o bibliotecas que logren este tipo de búsqueda de subcadenas escalable, y que funcionaría en un iPhone?

Answer 1

Aquí hay una serie de opciones diferentes. No conozco las marcas de referencia para cada una, así que tendrás que hacer algunas pruebas.

Primero está la extensión FTS3 a SQLite. Esto debe darle, búsqueda indexada rápida de texto: http://regularrateandrhythm.com/regular-rate-rhythm-blog/sqlite3-fts-in-IOS4.html

Entonces, ¿qué hay de las expresiones regulares que se introdujeron en el IOS 4:
http://developer.apple.com/library/ios/#documentation/Foundation/Reference/NSRegularExpression_Class/Reference/Reference.html

Para pre-IOS 4, puede utilizar RegexKitLite:
http://regexkit.sourceforge.net/RegexKitLite/index.html

Si decide utilizar expresiones regulares, a continuación, echar un vistazo a esta entrada en la forma de optimizar los:
How to speed up iPhone regular expressions with NSRegularExpression?

Answer 2

Quizás considere combinar su segundo enfoque con el enfoque asincrónico. Divida su gran bloque de texto en 5,10, sea cual sea el tamaño y búsquelos por separado con la misma cantidad de hilos. Luego combine los resultados utilizando un sistema de coordenadas que sepa cómo posicionar las coincidencias correctamente (por ejemplo, la zona 5 buscada por el hilo 5 y encontró una coincidencia en la posición 337 que se correlaciona con el documento x, posición y). Descubrirá que hay un límite en el que agregar más hilos no sirve, así que eso sería lo primero que se debe entender.

Answer 3

Si no puede tokenizar el texto (dividirlo en palabras) no puede indexarlo. Es por eso que LIKE es una búsqueda secuencial. A menos que su subcadena se pueda restringir de alguna manera (siempre soltar la primera letra o una longitud fija para la subcadena, por ejemplo) su texto no se puede almacenar como una lista de todos los tokens posibles y esos tokens no se pueden indexar. La clave (juego de palabras intencionado) es encontrar un algoritmo que produzca una lista suficientemente pequeña de tokens que el costo de indexarlos sea menor que el costo de una búsqueda lineal.