I have text documents which contain mainly lists of Items.Each Item is a group of several token from different types: FirstName. LastName, BirthDate, PhoneNumber, City, Occupation, etc.A token is a group of words.Items can lie on several lines.Items from a document have about the same token syntax, but they dont necessarely have to be exactly the same.They may be some more/less tokens between Items, as well as within Items.FirstName LastName BirthDate PhoneNumberOccupation CityFirstName LastName BirthDate PhoneNumber PhoneNumberOccupation CityFirstName LastName BirthDate PhoneNumberOccupation UnrecognizedTokenFirstName LastName PhoneNumberOccupation CityFirstName LastName BirthDate PhoneNumberCity OccupationThe goal is to identify the used grammar, e.g.FirstName LastName BirthDate PhoneNumberOccupation Cityand in the end identify all the Items, even thought they dont exactly match.In order to stay short and readable, let's use instead some aliases A, B, C, D, ... to designate those token types.e.g.A B CD FA B CD E FFA B CD E E FA C BD E FA B D CD E FA B CD E F GHere we can see that the Item syntax isA B CD E Fbecause it is the one that matches the best the sequence.The syntax (token types and orders) can vary a lot from one document to another.e.g. another document may have that listD AD ADD ABD AThe goal is to figure out that syntax without prior knowledge of it.From now, new line is considered as a token as well.A document can then be represented as a 1-dimension sequence of tokens:A B C B D A B C B B B C B A B C B A B C B A A C B A B C CHere the repeated sequence would be A B C B because it is the token that creates the least conflicts.Let's complexify it a bit.From now each token has no determined type.In the real world, we are not always 100% sure of some token's type. Instead, we give it a probability of having a certain type.Token 1  Token 2  Token 3  A 0.2    A 0.0    A 0.1  B 0.5    B 0.5    B 0.9     etc.  C 0.0    C 0.0    C 0.0  D 0.3    D 0.5    D 0.0Here is an abstract graphic of what I want to achieve:Solution considered A: Convolution of a patch of tokensThis solution consists in applying a convolution with several patches of tokens, and take the one that creates the least conflicts.The hard part here is to find potential patches to roll along the observe sequence.Few ideas for this one, but nothing very satisfying:Build a markov model of the transition between tokensDrawback: since a markov model has no memory, we will lose the orders of transition.e.g. If the repeated sequence is A B C B D, we lose the fact that A->B occurs before C->B.Build a suffix treeThis seems to be used extensively in biology in order to analyse nucleobases (GTAC) in DNA/RNA.Drawback: Suffix trees are good for exact matching of exact tokens (e.g. characters). We have neither exact sequences, nor exact tokens.Brute forceTry every combinaison of every size. Could actually work, but would take some (long (long)) time.Solution considered B: Build a table of levenshtein distances of suffixesThe intuition is that there may exist some local minima of distance when computing the distance from every suffix to every suffix.The distance function is the Levenshtein distance, but we will be able to customize it in the future in order to take in account the probability of being of a certain types, instead of having a fixed type for each token.In order to stay simple in that demonstration, we will use fixed-type tokens, and use the classic levenshtein to compute the distance between tokens.e.g. Lets have the input sequence ABCGDEFGH ABCDEFGH ABCDNEFGH.We compute the distance of every suffix with every suffix (cropped to be of equal size):for i = 0 to sequence.lengh  for j = i to sequence.lengh    # Create the suffixes    suffixA = sequence.substr(i)    suffixB = sequence.substr(j)    # Make the suffixes the same size    chunkLen = Math.min(suffixA.length, suffixB.length)    suffixA = suffixA.substr(0, chunkLen)    suffixB = suffixB.substr(0, chunkLen)    # Compute the distance    distance[i][j] = LevenshteinDistance(suffixA, suffixB)We get e.g. the following result (white is small distance, black is big):Now, its obvious that any suffix compared to itself will have a null distance. But we are not interested by suffix (exactly or partially) matching itself, so we crop that part.Since the suffixes are cropped to the same size, comparing long string will always yield a bigger distance than comparing smaller strings.We need to compensate that by a smooth penalty starting from the right (+P), fading out linearely to the left.I am not sure yet how to choose a good penalty function that would fit all cases.Here we apply a (+P=6) penalty on the extreme right, fading out to 0 to the left.Now we can clearly see 2 clear diagonal lines emerge. There are 3 Items (Item1, Item2, Item3) in that sequence. The longest line represents the matching between Item1 vs Item2 and Item2 vs Item3. The second longest represents the matching between Item1 vs Item3.Now I am not sure on the best way to exploit that data. Is it as simple as taking the highest diagonal lines?Let's assume it is.Lets compute the average value of the diagonal line that start from each token.We can see the result on the following picture (the vector below the matrix) :There are clearely 3 local mimima, that match the beginning of each Item.Looks fantastic!Now let's add some more imperfections in the sequence:ABCGDEFGH ABCDEFGH TROLL ABCDEFGHClearly now, our vector of diagonal averages is messed up, and we cannot exploit it anymore...My assumption is that this could be solved by a customized distance function (instead of Levenshtein), where the insertion of a whole block may not be so much penalized. That is what I am not sure of.ConclusionNone of the explored convolution-based solutions seem to fit our problem.The levenshtein-distance-based solution seems promising, especially because it is compatible with probability-based-type tokens. But I am not sure yet about how to exploit the results of it.I would be very grateful if you have experience in a related field, and a couple of good hints to give us, or other techniques to explore.Thank you very much in advance.
Recognize a grammar in a sequence of fuzzy tokens
data mining;clustering;text mining;time series;correlation