Un índice de autocoincidencia de texto completo comprimido es una estructura de datos que requiere menos espacio y es capaz de buscar patrones en el texto. También puede reproducir cualquier subcadena del texto, reemplazándolo efectivamente. A pesar de la reciente explosión de interés en los índices comprimidos, no ha habido mucho progreso en funcionalidades más allá de la búsqueda exacta básica. En este documento nos enfocamos en la búsqueda aproximada de cadenas indexadas (ASM), que es de gran interés, por ejemplo, en bioinformática. Estudiamos algoritmos ASM para índices comprimidos de Lempel-Ziv y para árboles/arreglos de sufijos comprimidos. La mayoría de los índices de autocoincidencia comprimidos pertenecen a una de estas clases. Comenzamos adaptando el método clásico de particionar en búsqueda exacta a los índices de autocoincidencia, y lo optimizamos sobre un representante de cualquiera de las clases de autocoincidencia. Luego, mostramos que un índice de Lempel-Ziv puede verse como una extensión del índice de -muestras clásico. Ofrecemos nuevas perspectivas sobre este tipo de índice, que pueden ser de interés independiente, y luego las aplicamos a un índice de Lempel-Ziv. Finalmente, mejoramos la verificación jerárquica, una técnica exitosa para la búsqueda secuencial, para extender las coincidencias de piezas de patrones hacia la izquierda o hacia la derecha. La mayoría de los árboles/arreglos de sufijos comprimidos admiten la bidireccionalidad requerida, lo que permite la implementación de la técnica mejorada. A su vez, la verificación mejorada reduce en gran medida los accesos al texto, que son costosos en los índices de autocoincidencia. Mostramos experimentalmente que nuestros algoritmos son competitivos y proporcionan intercambios útiles de espacio-tiempo en comparación con los índices clásicos.