Re: finding repeating patterns
On Sun, 27 Aug 2006 10:00:24 -0700 Rob Cozens [EMAIL PROTECTED] wrote: This started out as a mental exercise for moi, and the mouseUp logic is untested: ...snip... OTOH, working on it led me to the following offsets function, which has been tested. function offsets targetString, sourceString put empty into offsetsList put 0 into offsetAdjustment put length(targetString)-1 into targetLengthAdjustment repeat get offset(targetString,sourceString) if it = 0 then return offsetsList put (it+offsetAdjustment) return after offsetsList put it+targetLengthAdjustment into deleteCutoff delete char 1 to deleteCutoff of sourceString add deleteCutoff to offsetAdjustment end repeat end offsets Example: offsets(at,The cat in the hat smelled a rat where he sat.) returns 6 17 31 44 Note that the same logic can be applied to create lineOffsets, itemOffsets, and wordOffsets functions. Enjoy! Here's my version of the same thing -- I use it constantly. function multOffset str,ctr -- returns a comma-delimited list of all the offsets of str in ctr put into mosList put 0 into startPoint repeat put offset(str,ctr,startPoint) into os if os = 0 then exit repeat add os to startPoint put startPoint , after mosList end repeat if char -1 of mosList = , then delete char -1 of mosList return mosList end multOffset function multLineOffset str,ctr -- returns a comma-delimited list of all the lineOffsets of str in ctr put multOffset(str,ctr) into charList if charList = 0 then return 0 put the number of items of charList into nbr put into mlo repeat with n = 1 to nbr put the number of lines of (char 1 to (item n of charList) of ctr) , after mlo end repeat if char -1 of mlo = , then delete char -1 of mlo return mlo end multLineOffset -- Peter Peter M. Brigham [EMAIL PROTECTED] http://home.comcast.net/~pmbrig/ ~+~+~+~+~+~+~+~+~+~+~+~+~+~+~+~ My life has a superb cast, but I can't figure out the plot. ___ use-revolution mailing list use-revolution@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-revolution
Re: finding repeating patterns
All, Does anyone have (or know of) an algorithm to find repeating patterns of characters in a string ? This started out as a mental exercise for moi, and the mouseUp logic is untested: on mouseUp put field 1 into sourceString put empty into patternList put 6 into minPatternLength -- or whatever put length(sourceString) div 2 into maxPatternLength -- pattern can't be longer than half the length if maxPatternLength minPatternLength then exit mouseUp repeat with patternLength = maxPatternLength down to minPatternLength put ((length(sourceString) mod patternLength)-1)*patternLength into maxStartPosition -- pattern can't start within patterenLength-1 chars from end put patternLength - 1 into endAdjustment repeat with startingPoint = 1 to maxStartPosition set cursor to busy put startingPoint+endAdjustment into patternEnd put char startingPoint to patternEnd of sourceString into targetPattern if targetPattern is among the words of patternList then next repeat -- may need stronger checking? get the number of lines of offsets(targetPattern,char (patternEnd+1) to -1 of sourceString) if it 0 then put targetPatternitreturn after patternList end repeat end repeat put patternList end mouseUp OTOH, working on it led me to the following offsets function, which has been tested. function offsets targetString, sourceString put empty into offsetsList put 0 into offsetAdjustment put length(targetString)-1 into targetLengthAdjustment repeat get offset(targetString,sourceString) if it = 0 then return offsetsList put (it+offsetAdjustment) return after offsetsList put it+targetLengthAdjustment into deleteCutoff delete char 1 to deleteCutoff of sourceString add deleteCutoff to offsetAdjustment end repeat end offsets Example: offsets(at,The cat in the hat smelled a rat where he sat.) returns 6 17 31 44 Note that the same logic can be applied to create lineOffsets, itemOffsets, and wordOffsets functions. Enjoy! -- Rob Cozens CCW, Serendipity Software Company And I, which was two fooles, do so grow three; Who are a little wise, the best fooles bee. from The Triple Foole by John Donne (1572-1631) ___ use-revolution mailing list use-revolution@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-revolution
Re: finding repeating patterns
Here's my version: function getRepeatingPatterns tString,minLength,maxLength set the caseSensitive to true repeat with n = minLength to maxLength put empty into testString put 0 into charCount repeat for each char c in tString put c after testString get length(testString) if it n then next repeat if it n then delete char 1 of testString if space is in testString then next repeat -- optional if cr is in testString then next repeat -- optional add 1 to countArray[testString] end repeat end repeat repeat for each line L in the keys of countArray if countArray[L] 1 then put L countArray[L] cr after countList end repeat delete char -1 of countList sort lines of countList return countList end getRepeatingPatterns On 26 Aug 2006, at 23:23, jbv wrote: for those interested, here's something much faster : on mouseUp set cursor to watch lock screen put fld 1 into myST put number of chars of myST into n put into myL set the casesensitive to true put 1 into k repeat while k=1000 repeat with i=100 down to 6 put k+i-1 into b get char k to b of myST put myST into a replace it with in a put ((n - number of chars of a) / b) into c if c=2 then put it tab c cr after myL add b-1 to k exit repeat end if end repeat add 1 to k end repeat put myL end mouseUp ___ use-revolution mailing list use-revolution@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-revolution ___ use-revolution mailing list use-revolution@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-revolution
finding repeating patterns
Hi list, Does anyone have (or know of) an algorithm to find repeating patterns of characters in a string ? I'm not sure Transcript (er... Revolution) is fast enough for that kind of task, but anyway I thought it was worth asking... Thanks, JB ___ use-revolution mailing list use-revolution@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-revolution
Re: finding repeating patterns
well, I just realized that my question isn't very clear... I DON'T WANT to find how many times pattern ta appears in string tatata (for instance)... What I want to find is : is there any repeating pattern of chars in any string, which are they and (that's easy) how many times each pattern appears in the string... Hi list, Does anyone have (or know of) an algorithm to find repeating patterns of characters in a string ? I'm not sure Transcript (er... Revolution) is fast enough for that kind of task, but anyway I thought it was worth asking... ___ use-revolution mailing list use-revolution@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-revolution
Re: finding repeating patterns
On Aug 26, 2006, at 3:17 PM, jbv wrote: Does anyone have (or know of) an algorithm to find repeating patterns of characters in a string ? This brute-force method came to my mind. Decide on a min and max length of patterns. Try all possible substrings. (Outer loop is start position, inner loop is end char based on min max length. With each one check in an array. If not there put 1 otherwise increment. Look for counts greater than 1. If the repeating pattern must come right after the starting pattern, then this does not apply. In that case, just look for the repeats of the substring after the trial string. The problem is that xaxaxaxa would be counted as a repeating of xa and a repeating of xaxa. Dar Scott ___ use-revolution mailing list use-revolution@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-revolution
Re: finding repeating patterns
Dar, I came up to something similar... Here's a (very raw and quite slow) first approach (it checks only groups of 6 to 20 chars) : on mouseUp set cursor to watch lock screen put fld 1 into myST put into myL set the casesensitive to true repeat with k=1 to 1000 repeat with i=20 down to 6 put k+i-1 into b get char k to b of myST put myST into a replace it with in a put ((number of chars of myST - number of chars of a) / b) into c if c=2 then put it tab c cr after myL exit repeat end if end repeat end repeat put myL end mouseUp On Aug 26, 2006, at 3:17 PM, jbv wrote: Does anyone have (or know of) an algorithm to find repeating patterns of characters in a string ? This brute-force method came to my mind. Decide on a min and max length of patterns. Try all possible substrings. (Outer loop is start position, inner loop is end char based on min max length. With each one check in an array. If not there put 1 otherwise increment. Look for counts greater than 1. If the repeating pattern must come right after the starting pattern, then this does not apply. In that case, just look for the repeats of the substring after the trial string. The problem is that xaxaxaxa would be counted as a repeating of xa and a repeating of xaxa. Dar Scott ___ use-revolution mailing list use-revolution@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-revolution
Re: finding repeating patterns
for those interested, here's something much faster : on mouseUp set cursor to watch lock screen put fld 1 into myST put number of chars of myST into n put into myL set the casesensitive to true put 1 into k repeat while k=1000 repeat with i=100 down to 6 put k+i-1 into b get char k to b of myST put myST into a replace it with in a put ((n - number of chars of a) / b) into c if c=2 then put it tab c cr after myL add b-1 to k exit repeat end if end repeat add 1 to k end repeat put myL end mouseUp ___ use-revolution mailing list use-revolution@lists.runrev.com Please visit this url to subscribe, unsubscribe and manage your subscription preferences: http://lists.runrev.com/mailman/listinfo/use-revolution
