|
I registered to look at CUG. I didn't realize you could do that without charge ... Thanks.
According to the original article, the algorithm was oriented to detecting prohibited words in e-mail, so it quit once one of the banned words was found.
"The implementation in this article returns the offset within the string of the first matching substring and stops processing."
which is quite a bit different from what I am trying to do.
The article indicates that 0 and -1 have special meaning. I haven't stared at your code enough to be close to grok'ing it, but perhaps a 0 or -1 could be "moved up" the data structure related to a word that was matched, so that detection would be shortcut and proceed to the next letter with the state machine "cleared".
If there was no prefix with any other search word (such as looking for "hello" and "goodbye"), then it would be up near the "top". If there was a common prefix (as in my original question using the example "string" and "search"), then the state associated with 's' + 't' would be "shortcut/truncated" when "string" was found.
I was wondering if it would be simpler and still advantageous if the code could keep track of which words had been matched, and quit when they were all "hit". It wouldn't necessarily stop detecting previously matched substrings.
Thanks for taking the time to refresh your memory with this code, and considering a revision. It does seem like a worthwhile enhancement with broad applicability.
BTW, have you ever seen a C or C++ implementation of the Aho-Corasick algorithm for detecting multiple sub-strings in a string? I'm only aware of that algorithm, and my understanding is that it also uses a FSM approach.
As they say, "if this stuff was easy, it wouldn't pay so well. (written by a freeware developer to a software contributor <g>)
|
|
|
|
|
I was not familiar with that algorithm before, although I know the name Aho to be the 'a' in the famous "awk" Unix utility (Weinberg and Kernighan, also of great Unix fame are the 'w' and 'k'). Upon cursory examination, their algorithm appears very similar to the Halibard-Rubin one upon which my classes are based. Interestingly, they reference Kernighan's spam filter as an inspiration to their work.
There is a CP article (http://www.codeproject.com/csharp/ahocorasick.asp) that may interest you if you haven't already seen it.
At this time, I'm not interested in enhancing my classes (for free, at least). Especially since there are so many other similar pieces of code out there. It would be a simple matter to keep track of which words have been hit, but a performance drain to detect when all have been hit -- at least given what my imagination has conjured so far.
Scot Brennecke
Software Developer
VC++ MVP
|
|
|
|
|
l_d_allan, did you ever locate a solution? Because I too am looking for the same thing: a class/procedure that returns true if each token exists in the search string. Ideally, I don't care how many times a token is present, so it seems a short-circuited logic works best: when a token is found once, we stop searching for that one. But, I guess that's a bit different from how FSM works.
|
|
|
|
|
I have not spent a lot of time viewing the code, but it appears that the efficient part of this procedure is the 'looking' for the substring. Creating new FSM from words/substrings of interest appears not to be expensive.
So here is my suggestion. Use FindFirstIn to locate the first substring. Now create a new 'problem' with the rest of the original string from the point where substring was found. Create a new FSM with one less substring and start a new search. Repeat the process till all the words/substrings have been found. You do not have to make any changes to the class or the search procedure to do this.
|
|
|
|
|
please help me to add a CSTringList to an object of CIVstringSet.I tried to use the overloaded member function ADD(CStringList list);but an error is being shown.IT says that "cannot convert from CStringList to const char *);
moreover the Add() function is taking too much time to add all the CString to the list when i pass a CString as a parameter to the ADD function.
WHY cant i use the overloaded member function ADD(CSTringLIST list);plz reply as i am facing a deadline.
|
|
|
|
|
Are you using a CStringList object, or perhaps a pointer to a CStringList? The function requires a direct reference to the object, not a pointer. You are using the MFC version of the class, and not the STL version, right?
As concerns "taking too much time", can you be more specific? Have you identified which step is taking the most time?
Scot Brennecke
Software Developer
VC++ MVP
|
|
|
|
|
Excellent bit of code however I used it to search for 1400 substrings in a short bit of text (a url) and it fell over because the DFA it builds gets too large.
I think the large space requirement for many substrings in inevitable but if anyone knows otherwise I'd love to know.
|
|
|
|
|
you can dramatically increase the number of strings this class can handle by changing
the array m_apnFSM to be some STL dynamically-allocating type, and using that template-class's dynamic allocation mechanisms in favor of the SetColDim method -- this should also be faster
if you're adding a large number of strings, as the original increases by a small static amount each time it re-allocs, and the STL libraries try to amortize the cost of memory allocation.
with that change it seems to scale to around 80,000 strings on my machine.
(i used a deque<vector<dword[128]> >, as the [] operator is a little faster for vector, but deques are faster if you keep forcing the collection to allocate more memory).
|
|
|
|
|
Hi
There is a bug in the STL version of the code
IT reads
int CIVStringSet::Add( LPCTSTR pszWords, LPCTSTR pszDelims )
{
.....
// Now, move beyond the token just extracted and the delimiters
int nTokenLen = strToken.length() ;
if ( nTokenLen < strUnparsed.length() )
{
int nDelimLen = _tcsspn( &strUnparsed[nTokenLen], pszDelims ) ;
nTokenLen += nDelimLen ;
if ( nTokenLen < strUnparsed.length() )
strUnparsed = strUnparsed.substr( nTokenLen ) ;
else
break ;
}
else
break ;
.......
which gets stuck in a loop by this line
int nDelimLen = _tcsspn( &strUnparsed[nTokenLen], pszDelims ) ;
it works with this instead though.
.......
// Now, move beyond the token just extracted and the delimiters
int nTokenLen = strToken.length() ;
if ( nTokenLen < strUnparsed.length() )
{
int nDelimLen = strUnparsed.find_first_not_of( pszDelims , nTokenLen ) ;
//nTokenLen += nDelimLen ;
if ( nDelimLen < strUnparsed.length() )
strUnparsed = strUnparsed.substr( nDelimLen ) ;
else
break ;
}
else
break ;
.........
Thanks for a reaaly useful class though.
Spencer
|
|
|
|
|
Hi there ,
Your example is great , I'm wondering if you have any implmentation for unicode strings . If no can you point me how this can be done ?
WBR Oleg
|
|
|
|
|
Oleg,
I have not needed to adapt this to Unicode. This could be adaptable to Unicode strings by substituting wchar for char in the code. However, there is an assumption that only 128 characters are in the alphabet, as we only allocate 128 arrays and mask out indexes above 0x7F. With some small effort, I think you could do it.
Scot Brennecke
Software Developer
VC++ MVP
|
|
|
|
|
I am designing a Postscript editing program, which will search through the Postscript text file looking for a particular string. The problem I am having is the amount of time it is taking to search each line for the string. Is there any way of speeding this up, and not looking at each line, maybe somehow "jump" to the correct place in the file?
Any advice would be appreciated.
Bryster
|
|
|
|
|
As an example string to search through....
"Joshua Lewis soll nicht so machen als ob er das kann, sondern wie alle kinder sollen sie lieb sein"
(The german grammer is horrible I know , my english also )
And as the substrings/words to be found are "so sollen wie er"
The results shown in the dlg app are..
so,so,er,so,er,wie,er,so...
soll and sollen were found, but not as complete words.
Is there any was the the parser can tell the difference between partial complete words?
I´m no genius, and therefore can only guess that once a substring has been found, it is "marked as being found", and the parser continues with the next token in the string to be searched.
Is there a way to "force" the parser to continue so that "full" words are also found?
bum... and I thought I´d got rid of all the bugs
|
|
|
|
|
Found a (semi) solution for this problem
if ( dwEntry > MAXWORD ){
int nTmpIndex = nIdx;
if((!(nTmpIndex++ > m_strSearch.length()) && m_strSearch[nTmpIndex] == ' ')
|| nTmpIndex == m_strSearch.length())
{
int nIndex = HIWORD(dwEntry) - 1 ;
ASSERT(nIndex < size());
rnNext = nIndex ;
m_nCurTextChar = nIdx + 1 ; // set the index for the next time
break ;
}
else{
// did not find a complete word
wCurState = LOWORD(dwEntry);
}
}
Changed this in the function FindNext( int & rnNext )....
This only returns COMPLETE words that have been found, maybe a flag or something to differenciate between partial and full word search and replace...??
bum... and I thought I´d got rid of all the bugs
|
|
|
|
|
I thought of porting the class to Java, as I find it useful. During the process I found that it uses DWORD as a container for (non-defined) structs.
This makes the algorithm less then obvious, not to mention cumbersome to port.
C++ is blessed with all that is required to make the algorithm both readable and efficient, so why not use it?
Apart from that - great class.
|
|
|
|
|
It took me several minutes of head-scratching before I finally made sense of what you meant by "uses DWORD as a container for (non-defined) structs.". At least, I think I now know to what you refer. . . I assume you mean that you don't approve of using the arrays of DWORDS m_apnFSM, rather than having arrays of some struct with two smaller integers. The fact is that after reading the article upon which my class is based, I had no trouble understanding the algorithm, so it never occurred to me to divide the DWORD into two variables. The original did not do this, and I didn't feel compelled to improve on it in that way.
As for porting this class to Java. . . well, I can't say that I see the wisdom. The whole idea was to make a class that was fast. And, we all know that Java is not known for its efficiency.
Nevertheless, if you feel inclined to make these changes and port to Java, I won't protest.
Scot Brennecke
Software Developer
VC++ MVP
|
|
|
|
|
Hi - love the article !! more often however, I need to know WHERE ie by character position a particular string was found !!
Is there a way to return this from the FSM ?? I dont have the base CUJ article, maybe it had notes there - I will try to find a copy (June 2002 may not even be out 'Down-Under' here in Aus yet/hopefully)
In General, Im using Multiple Regular Expressions To (For Example) Split a report
so (re's in brackets)
(^1) Matches a page-break
(^0UserId: ABCDEFG) Indicates The Start Of Data
(**** End Of Report ****) Is The End Of The Data, as long as the start has been found (ie there are multiple reports in the one file)
so I have to apply each RegEx to each line to keep track of where in the report I am (thats a lot of work). The multiple string search you present is a possible improvement, but not without knowing that the '1' for the Page break was in Column 0.
Its probably a waste to use such an efficient search tool on this sort of thing, given thats I have to track through the file line by line - brute force may be easiest option....
Thanks anyway
Cheers, Garth
|
|
|
|
|
Garth,
I must admit that I feel kinda silly for not providing that information! Looking at the FindNext function, the data you want is readily available (in nStartChar). The trick then becomes in deciding the best way to return the position. For the FindFirstIn and FindNext, we could simply change the return type from bool to int, and return the position. We would then return -1, rather than false, to indicate no more tokens are found. As for FindAllIn, however, we build a CStringList with the found tokens. We could have another array as a third parameter which would be filled with corresponding positions. Or perhaps, embed the position in the strings, using a delimiter. Or, we could just not return the postions at all.
I encourage anyone with an opinion on the matter to "speak up".
The real benefit of this class is seen when searching a large text and/or with a large number of seek words. For searching small strings for a small number of words, it may not be worth the overhead. I haven't taken the time to analyze the performance metrics to determine what the threshhold is, but I suspect short lines such as yours may not warrant this. Even so, you may find this class easy enough to use that it's worth the overhead.
Scot Brennecke
Software Developer
VC++ MVP
|
|
|
|
|
Scot - thanks for your reply - dont worry about not providing the info - I thought it might have been an obtuse question, but was prepared to ask anyway (and felt more of a goose for not being able to find it myself)
I agree with your synopsis for fixing the returned positions for FindFirstIn and FindNext - and even have a suggestion for FindAllIn .. instead of CStringList, how about an STL vector - 2 thoughts on its contents ..
1) the matched string and its position
ie (("quick", 4), ("fox", 14)) If I specified "quick" & "fox", but, since these strings are trivial and the real world wont be, this may be too much info to return - a better idea would appear to be :-
2) An index into the string array of strings to match (CIVStringSet) and the position the string was found at, ie
search for "men", "country", "rabbit", specified in that order, returns :-
((0, 20),(1, 50),(1, 80),(1, 90), (2, -1))
where 0 is the element in the list "men" and 1 is the element "country" etc
(the positions returned I used are not real - I was too lazy to count along the string) .. note how a) '1' for country is returned three times, since there are three occurences, and b) since "rabbit", ie element 2 wasnt found, it's vector element returns -1 ??
well, those are my thoughts .. Im not fantastic on STL, just learning, so it might take me a while to implement any of this
Thanks for your help anyway, It's still a great article !!
cheers & thanks
Garth
|
|
|
|
|
An excellent idea!
I like your idea of simply returning the index into the array of the found token. Since these strings are already known (the user added them), there's really not much sense in my plan of creating a new string to return. The index should be sufficient.
If you agree, then, the solution would be to create a simple struct, or even an STL pair, that contains the index into the array, and the position at which found. The FindAllIn function would then return an array of such pairs or structs.
Scot Brennecke
Software Developer
VC++ MVP
|
|
|
|
|
I'd suggest returning a vector of 'match' objects (a simple struct) that would be indexed by the strings you are searching for an contain the index into the string being searched:
CIVStringSet SearchSet;
SearchSet.Add("FindMe");
Matches matches = SearchSet.FindAll(szStringToSearch);
for (int i = 0 to matches.Length)
Print "Found " + match.Text + " at position " + match.pos
Print "Found string at " + matches["FindMe"].pos;
cheers,
Chris Maunder
he was a VB programmer, but he got better - Christian Graus
|
|
|
|
|
An excellent idea (of course)!
However, I also like Garth's idea of simply returning the index into the array of the found token. Since these strings are already known (the user added them), there's really not much sense in my plan of creating a new string to return. The index should be sufficient.
If you agree, then, the solution would be to create a simple struct, or even an STL pair, that contains the index into the array, and the position at which found. The FindAllIn function would then return an array of such pairs or structs.
Scot Brennecke
Software Developer
VC++ MVP
|
|
|
|
|
Sounds ok Scot .. maybe STL vector of simple elements is overkill (the STL part anyway) - the 'kiss' principle should reign .. A CArray object might be more preferable, since STL isnt used anywhere else, it might add more overhead ...
Just went looking for the June 2002 CUJ, couldnt find it in 4 newsagents around town that just gives me the excuse to go to Borders tonight
Garth
|
|
|
|
|
My experience with STL is that it is lightweight, and more efficient than MFC classes. But it is also harder to read and use for the uninitiated. I'm certain that my CIVStringSet class would be a lot faster if I used std::string and vector instead of CString and CStringArray. But I made the choice for ease of use to balance with the efficiency of the algorithm.
Unless you or someone else has another more compelling reason not to, I'm leaning toward returning a std::pair<int,int> with the index of the string and its position from the FindFirstIn and FindNext methods, and a vector of the same from FindAllIn.
I may even make another class that uses STL instead of MFC, as an alternative for those who don't want the MFC baggage.
Scot Brennecke
Software Developer
VC++ MVP
|
|
|
|
|
Scot Brennecke wrote:
you or someone else has another more compelling reason not to
me ? I'm a rank beginner - hardly experienced enough to advise someone of your calibre to suck eggs.. I merely thought - perhaps a tad naive, that if one was writing a 'component' for other people, you'd write it all STL or all MFC, but not mix them .. as I said, that may be a tad naive, thats not meant to look or sound like a criticism ...
just because the STL version (or STL in general) may be harder to use, I'm all in favour of learning it where the gain outweighs the pain - so if someone presents a 'free' component, for example off CP, and it uses STL, and I dont know that much about STL, I'd do my damndest to learn enough to use that component .. (hopefully the example supplied would show most of it)
<rant>
I think (generalisation) that some people complain too much about stuff from CP, when they should remember thats it's free, save for a bit of work learning new tricks .. me, Im just grateful of all the help and ideas one gets !!!
Garth
|
|
|
|
|