I'm working with a pattern matching algorithm that generates an acyclic finite state automaton that accepts a given text string and all its substrings. The FSA algorithm is being run on a symbolic representation of a music stream (e.g., MIDI data). The music stream has been preprocessed to divide each song into unlabeled 'segments'. An FSA is generated for each segment in each song: if I have $n$ songs, each divided into $y$ segments, I will have $n \cdot y$ separate FSAs.

I would like to compare each segment's FSA with the other FSAs in my corpus. The ultimate goal would be to do clustering within a similarity space and come up with 'classes' of segments according to how similar their construction metrics are. Thus, of particular interest are the grammars that each FSA defines (corresponding roughly certain components of the musical content in the segment). Are there techniques that might be good for comparing something like this? KL-divergence comes to mind (e.g., using it compare the distribution over strings associated with a given FSA), although there may be better/more efficient techniques?

Also, apologies if this question is either (1) trivially easy or (2) indicative of some deeper misunderstanding or (3) answered elsewhere. I'm a real nub, folks!

  • 3
    $\begingroup$ You'll need to tell us what you mean by "similar". You have to select the metric; there is no one right metric that is right for all purposes. Without more information, we can't tell you what metric to use. I suggest editing the question to explain why you want to measure similarity, what you will do with the results of the similarity metric, and what research you have done. You might start by looking at measures of similarities between the underlying strings, rather than measuring the similarities of the FSAs derived from those strings. Edit distance comes to mind. $\endgroup$ – D.W. Sep 10 '14 at 4:46
  • $\begingroup$ There are many string metrics; which works for you depends. (Note: some of the string "metrics" listed in that article are not actually metrics in the mathematical sense.) $\endgroup$ – Raphael Sep 10 '14 at 8:41
  • $\begingroup$ String metrics are good, but not quite what I'm after. Instead of comparing specific strings to one another, I'd like to compare the system of rules (the formal grammars/FSAs) that could have produced those strings. I recognize that there are infinitely many grammars that can produce any specific string, so I'm constraining my search to a grammar (FSA) constructed using a particular set of rules. I imagine there might be cases where two individual strings are formally similar according to a given string metric, but the grammars required to produce them are quite different $\endgroup$ – flip Sep 10 '14 at 20:28
  • $\begingroup$ From the statement of the problem, each FSA is accepting one string and all its substrings. Fundamentally, this FSA is characterized by the longest string it accepts. Its whole structure derives from it. Hence there is little point in comparing the FSA rather than directly comparing the strings they are constructed from. It may be that your FSA construction technique emphasizes some features, which you consider important. Then we need to know what they may look like so as to understand what matters. It comes back to: what is similar, what metric. As it is, this question makes no sense. $\endgroup$ – babou Aug 11 '15 at 8:56

you might have more luck from another angle & looking into research into music piece similarity, there are researchers studying that, and while your approach can work, there are other approaches. there are large databases that look at many elements/ criteria such as lyrics, genre etc. eg Music genome project.

sometimes when theres a wide variety of algorithms a survey can help. here are two surveys on graph matching.

| cite | improve this answer | |

Since FSAs are directed graphs, your question can be generalized as "algorithm for measuring similarity between directed graphs". A google search for "graph similarity algorithm" gives pages and pages of hits, maybe one of those would be suitable for your purposes?

Once difference between FSAs and general digraphs are the edge labels, or transition symbols in FSAs, so you would have to modify these algorithms to take that into account.

| cite | improve this answer | |
  • $\begingroup$ A method like this will miss some key properties. For example, you probably want different representations of the same language to have complete similarity, but comparing the graphs could report two automata for the same language as dissimilar. $\endgroup$ – jmite May 7 '16 at 5:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.