Compara rápidamente una cadena contra una colección en Java

Estoy tratando de calcular las distancias de edición de una cadena contra una colección para encontrar la coincidencia más cercana. Mi problema actual es que la colección es muy grande (alrededor de 25000 elementos), así que tuve que reducir el conjunto a solo cadenas de longitudes similares, pero eso solo reduciría a unos pocos miles de cadenas y esto todavía es muy lento. ¿Existe una estructura de datos que permita una búsqueda rápida de cadenas similares o existe otra forma de abordar este problema?Compara rápidamente una cadena contra una colección en Java

Fuente

2012-02-04 Lezan

¿Cómo te va ahora? ¿Puedes mostrar un código? –

Define "similar". –

Me refiero a la comparación de palabras que son errores de ortografía comunes, tales como "exanple" y "example" o "strange" and "wierd". – Lezan

suena como un BK-tree podría ser lo que quieres. Aquí hay un artículo sobre ellos: http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees. A quick Google produce algunas implementaciones de Java.

Fuente

2012-02-04 08:50:22 SimonC

Gracias, lo buscaré y le contaré cómo va, ¡gracias! – Lezan

¡Sí que lo hizo, necesitaba una implementación diferente de la búsqueda, pero fue perfecto! ¡¡Gracias!! – Lezan

Si sus criterios para 'similar' definen un total de pedidos, usted debería poder definir un Comparador y usar un TreeSet para encontrar las coincidencias más cercanas (por ejemplo, usando los métodos de techo y piso).

Fuente

2012-02-04 08:42:32

Levenshtein Automata permite la selección rápida de un conjunto de palabras de un diccionario grande de modo que estén dentro de la distancia dada de Levenshtein de una palabra determinada.

Ver: Schulz K, Mihov S. (2002) Fast String Correction with Levenshtein-Automata.

Fuente

2012-02-04 10:32:52 kkm

Compara rápidamente una cadena contra una colección en Java

Respuesta

Cuestiones relacionadas