¿Método para medir la 'similitud' entre las gramáticas de la FSA?

10

Estoy trabajando con un algoritmo de coincidencia de patrones que genera un autómata de estado finito acíclico que acepta una cadena de texto dada y todas sus subcadenas. El algoritmo FSA se ejecuta en una representación simbólica de una transmisión de música (por ejemplo, datos MIDI). La transmisión de música se ha preprocesado para dividir cada canción en 'segmentos' sin etiqueta. Se genera una FSA para cada segmento en cada canción: si tengo canciones, cada una dividida en segmentos, tendré FSA separadas.nyn⋅y

Me gustaría comparar la FSA de cada segmento con las otras FSA de mi corpus. El objetivo final sería agrupar dentro de un espacio de similitud y crear 'clases' de segmentos de acuerdo con lo similares que sean sus métricas de construcción. Por lo tanto, de particular interés son las gramáticas que define cada FSA (que corresponden a ciertos componentes del contenido musical en el segmento) ¿Existen técnicas que podrían ser buenas para comparar algo como esto? Me viene a la mente la divergencia de KL (p. Ej., Al usarla, comparar la distribución sobre las cadenas asociadas con una determinada FSA), aunque puede haber técnicas mejores / más eficientes.

Además, disculpas si esta pregunta es (1) trivialmente fácil o (2) indicativa de algún malentendido más profundo o (3) respondida en otra parte. Soy un verdadero nudo, amigos!

formal-languages reference-request finite-automata dar la vuelta
fuente
3
Deberá decirnos qué quiere decir con "similar". Tienes que seleccionar la métrica; no hay una métrica correcta que sea correcta para todos los propósitos. Sin más información, no podemos decirle qué métrica usar. Sugiero editar la pregunta para explicar por qué desea medir la similitud, qué hará con los resultados de la métrica de similitud y qué investigación ha realizado. Puede comenzar mirando medidas de similitudes entre las cadenas subyacentes, en lugar de medir las similitudes de las FSA derivadas de esas cadenas. Editar distancia viene a la mente.
DW
Hay muchas métricas de cadena ; lo que funciona para ti depende. (Nota: algunos de la cadena "métricas" enumerados en este artículo no son en realidad métricas en el sentido matemático.)
Rafael
Las métricas de cadena son buenas, pero no exactamente lo que busco. En lugar de comparar cadenas específicas entre sí, me gustaría comparar el sistema de reglas (las gramáticas formales / FSA) que podrían haber producido esas cadenas. Reconozco que hay infinitas gramáticas que pueden producir cualquier cadena específica, por lo que estoy restringiendo mi búsqueda a una gramática (FSA) construida utilizando un conjunto particular de reglas. Me imagino que puede haber casos en los que dos cadenas individuales están de acuerdo formalmente similar a una cadena dada métrica, pero las gramáticas requerido para producirlos son muy diferentes
flip
A partir de la declaración del problema, cada FSA está aceptando una cadena y todas sus subcadenas. Fundamentalmente, esta FSA se caracteriza por la cadena más larga que acepta. Toda su estructura deriva de ella. Por lo tanto, tiene poco sentido comparar la FSA en lugar de comparar directamente las cadenas a partir de las cuales están construidas. Puede ser que su técnica de construcción de FSA enfatice algunas características, que considera importantes. Entonces necesitamos saber cómo se verán para entender lo que importa. Vuelve a: qué es similar, qué métrica. Tal como están las cosas, esta pregunta no tiene sentido.
babou

Respuestas:

1

es posible que tenga más suerte desde otro ángulo y al investigar la similitud de la pieza musical, hay investigadores que lo estudian y, aunque su enfoque puede funcionar, existen otros enfoques. existen grandes bases de datos que analizan muchos elementos / criterios, como letras, géneros, etc., por ejemplo, proyecto de genoma musical .

a veces, cuando hay una gran variedad de algoritmos, una encuesta puede ayudar. Aquí hay dos encuestas sobre correspondencia de gráficos.

vzn
fuente
0

Dado que los FSA son gráficos dirigidos, su pregunta puede generalizarse como "algoritmo para medir la similitud entre los gráficos dirigidos". Una búsqueda en Google de "algoritmo de similitud de gráficos" proporciona páginas y páginas de resultados, ¿tal vez una de ellas sería adecuada para sus propósitos?

Una vez que la diferencia entre los FSA y los dígrafos generales son las etiquetas de borde, o los símbolos de transición en los FSA, entonces tendría que modificar estos algoritmos para tener eso en cuenta.

Mike Ounsworth
fuente
Un método como este perderá algunas propiedades clave. Por ejemplo, es probable que desee que las diferentes representaciones del mismo idioma tengan una similitud completa, pero al comparar los gráficos podría informar dos autómatas para el mismo idioma que no sean similares.
jmite