Hello I am looking for an algorithm which solves following problem for me.

Given a text/string = 'BIRDBIRDBIRDBIRDDEVILDEVILDEVILDEVILEASYEASYEASY ...' of an unkown language. For the sake of simplicity I used english words, so that you can immidiately see what the words are, but normally I deal with an unkown unnatural language. We can assume that if a patter/word appears, then it appears frequently.

I want to search for patterns/words appearing in the string. So, we basically put parenthesis around the letters in the text, e.g. '(BIRD)(BIRD)(BIRD)(BIRD)(DEVIL)(DEVIL)(DEVIL)(DEVIL)(EASY)(EASY)(EASY) ...' This would decompose our text in words which reflects intuitively the pattern of the text. An natural question arises: How to choose the words of that unkown language?

I know Machine Learning Algorithms are good for searching for unkown pattern. But I cannot use ML, since I wont have data to train... I tried then to formulate my problem mathematically. I came up with the condictions, that 1. We want as few different words as possible (so use some threshold) 2. We want that a word is appearing as often as possible (so use some threshold). My intuition tells me, that these two conditions may help me to find the pattern.

So, does anyone know what kind of mathematical/computer scientific field I should study or are the any algorithm which can solve my problem?

I am new to computer science, so it would be nice if you can help me out :)

Greetings mathemagier

  • $\begingroup$ Use suffix tree, Ukkonen algorithm and take maximal non repeating strings with some multiplicity. $\endgroup$ – Evil Jan 17 at 10:34

Your Answer

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

Browse other questions tagged or ask your own question.