Need help developing a string search algorithm

[TheJokerV]

OK so here's the problem, I have 2 files: a large text file with a wide assortment of words, and a large dictionary file containing all valid english words. I have to develop an algorithm which would check and count the number of valid english words in the large text file. OK so i know this is basically a string search problem. Using the naive search would basically never end. I though about using the finite state machine search but I'm having a little trouble with how to implement the machine.(preprocessing doesn't count BTW) I also thought about the KMP algorithm. Anyway I don't want people to write the programm for me but I woudl like a little general guidance so does anyone have any ideas?

 

[mikeblas]

Why would the naive search never end? It would end after the last word from the file is searched.

I'd read the dictionary and sort it. Then, I'd read each word from the input file and try to find it in the list. Since the list is sorted, the search is O(log2) for n words in the dictionary, so m words in the input file gets O(m*log2).

Since you're just comparing for equality and not substrings of a larger string, I'm not sure how KMP would be applied.

 

[ameoba]

How big is 'large'?

 

[nameless_centurian]

mikeblas, i am not understanding why the search time is not O(K*m*log2), with K = number patterns, m = max length of pattern, n = number of dictionary entries? unless we are assuming an LCP array, then we can do it in O(k*(log2 + m)), but it seems like an awful lot of rather slow preprocessing to get a string search that runs slower than the aho-corasick method the OP mentioned.

OP, have you ever worked with tree structures before? the FSA method you are talking about is actually rather easy to implement if you have.

you COULD append all of the words in the dictionary together and run KMP on that. this would yield the O(K*|dictionary|) where K is number of search patterns and |dictionary| means "the length of the dictionary".... but this seems like a rather slow algorithm!

 

[mikeblas]

Why is the number of patterns a factor?

OK so here's the problem, I have 2 files: a large text file with a wide assortment of words, and a large dictionary file containing all valid english words. I have to develop an algorithm which would check and count the number of valid english words in the large text file.

The problem is to read a string and see if it is in a dictionary. Then read the next string, and probe the dictionary again.

Say the input file is: "The quick brown fox jumped over the lazy dog."
And the dictionary file is "brown dog fox jumped lazy".

The first word is "the", and we probe the dictionary. Not there, the count isn't incremented. We read the next word; "quick". It's a hit, so the count is incremented. And so on. The probing of the dictionary is O(log2), since we can make a tree of it or binary search. Doing that probe for m words leaves us at O(m*log2).

I don't see how KMP would be applicable to this problem. Building a A-C style trie would be interesting, though, and I think it might reduce the problem to O. But I don't think this is the general form of A-C. The idea would be to not probe the list with the whole string, but move down a trie--a 26-way tree, really--with each character read.

 

[TheJokerV]

OK so mike you are right, but I think you need to know some additional details. The dictionary file contains all the valid english words (somewhere around 35K+ words). The text file is a standard text file except its 826 MB big. Yea that's alot, so having a naive algorithm verses a more advanced algorithm could mean the difference between weeks and day. Now decided to spend the last 10 hours going the finite state approach and I think I've developed something nice except it has one MAJOR bug which I can't seem to solve. First here's my code:

CTree.h

#ifndef CTREE_H
#define CTREE_H

#include <iostream> 
#include <cstdio> 

class CTree
{
public: 
	CTree();
	CTree * makenext(char);              //creates a new CTree to corresspond to a char if there isn't one and returns the address of the next CTree 
	bool returnisword();                       //returns isword 
	void setisword(bool val);            //set the value of isword
	CTree * isnext(char nextchar);       //returns NULL if no CTree char next
private:
	bool isword;
	CTree *nextchar[26];
};

#endif

CTree.cpp

#include "CTree.h"

CTree::CTree(){
	isword = false;
	for(int i = 0; i < 26; i++){
		nextchar[i] = NULL; 
	}
}

bool CTree::returnisword(){
	return isword;
}

void CTree::setisword(bool val){
	isword = val;
}

CTree * CTree::isnext(char nchar){
	if(nextchar[nchar-97] != NULL){
		return nextchar[nchar-97];
	}else{
		return NULL;
	}
}

CTree * CTree::makenext(char nchar){
	if(nextchar[nchar-97] != NULL){
		return nextchar[nchar-97];
	}else{
		CTree *foo = new CTree;
		nextchar[nchar-97] = foo;
		return nextchar[nchar-97];
	}
}

main.cpp

#include <vector>
#include <fstream>
#include <string>
#include <stdio.h>
#include "CTree.h"

using namespace std;

CTree mytree;	
int wordcount = 0;

void builddictionary(){
	string word;
	ifstream input("dictionary.txt");
	
	CTree *treepointer = &mytree;
	if(input.is_open()){
	while (!input.eof()){
		input>>word;
		for(int i = 0; i < word.length(); i++){
			treepointer = treepointer->makenext(word.at(i));
			if(i == (word.length()-1)){
				treepointer->setisword(true);
			}
		}
		treepointer = &mytree;
	}
	}
	input.close();

}


void numwords(){
	string word;
	int c;
	CTree *treepointer = &mytree;
	vector<CTree*> possiblewords;
	vector<CTree*>::iterator it;

	ifstream input("text.txt");
	if(input.is_open()){
		do{
			c = input.get(); //gets the new charcater
			if((c >= 65)&&(c <= 90)){
				c += 32;
			}
			if((c >= 97)&&(c <= 122)){
				possiblewords.push_back(&mytree);
				for(it = possiblewords.begin(); it!=possiblewords.end(); it++){
					*it = (*it)->isnext(static_cast<char>(c));
					if(*it == NULL){
						possiblewords.erase(it);
						it = possiblewords.begin();
					}
					if((*it)->returnisword() == true){
						wordcount++;
					}
				}
			}else{
				possiblewords.erase(possiblewords.begin(), (possiblewords.begin()+possiblewords.size()));
			}
		}while(c != EOF);
	}
}
int main(){
	builddictionary();
	numwords();
	cout << wordcount << endl;
}

Also I'm using a lighter dictionary and text file for debugging purposes so for those of you that want to try this out here they are:

dictionary.txt

ab
abab 
some
something
new

text.txt

absdafsdoignabababnickskdfbvkv ejfnsukdbvfsjkdbvfsuibvfwsehfbvjhwf sdvsvsadvf

SO basically my program works by first making a finite state machine from the dictionary and then using a vector to go through and count all the English words. I get the following error: "Expression: vector iterator not dereferencable". Now i think I know what the problem is, I'm tryign to delete the vector element which is NULL but I need to do this because once the tree comes back NULL it means that there are no more English words to be derived by that string of characters. I'm about to collapse from exhaustion but maybe someone can see what I'm missing and maybe give me a little guidance. Thank you so much guys for helping me out.

 

[mikeblas]

The dictionary file contains all the valid english words (somewhere around 35K+ words). The text file is a standard text file except its 826 MB big.

I'm not sure how these additional details would change my thinking.

Yea that's alot, so having a naive algorithm verses a more advanced algorithm could mean the difference between weeks and day.

I'm well aware of that, obviously. I'd point out to you that choosing the correct algorithm is far more important than choosing the right algorithm. If you don't have the right approach to the problem, you won't be able to finish writing the code in the first place. DNS is certainly worse than a last place finish; fishing with the wrong answer is also less desirable than slowly finding the correct result.

Is there a place where I can download your data files? Have you really estimated the runtime for your scenario to be a day? On what kind of hardware? It seems that you should be able to process this data about as fast as you can read it from disk; so if you can read at 30 megs per second from your drives, you should be able to eat up 825 megs in less than half a minute.

it has one MAJOR bug which I can't seem to solve. First here's my code:

I'm not sure you've got only one bug.

As a style point, it looks like you've got lots of magic numbers foating around. It turns out you can use some standard functions for the character manipulation you're doing, and you can compare against character literals directly. For example, I'd rewrite this code:

                       if((c >= 65)&&(c <= 90)){
                               c += 32;
                       }
                       if((c >= 97)&&(c <= 122)){

to use tolower() and 'a' and 'z' in place of 97 and 122.

I can't quite figure out how your loop is meant to work. I don't see where you find word breaks, for example. I also don't understand how you'll handle words like "it's" where an apostrophe appears; or hyphenated words. Given the input you show in your post, what words will you try to look up in your dictionary?

The code you have is looping over a vector of pointers to tree nodes, and I'm not sure why you need to save those nodes as you walk the tree.

You don't mention if the error you get is at runtime or compile time, and you've not told us which tool set you're using on which operating system, so I'm a little in the dark with helping you out. But the line of code I expect you're asking about this one:

*it = (*it)->isnext(static_cast<char>(c));

which I can't quite understand. I'm not sure why you use the static_cast operator here. The CTree::isnext() member will return a pointer to a CTree object, not an iterator. The error doesn't seem to have anything to do with the return value being NULL; it's that you can't assign something to an iterator type that's not, itself, an iterator. You're trying to dereference the iterator to make it a type of the object that you're assigning to it, but that doesn't work either; the iterator can't be expected to iterate over arbitrary objects--particularly not those that aren't in an iteratable collection.

I think you'll find that this loop isn't necessary in the first place--at least, now as it's written. You should just be walking through the tree as you get new characters, and the possiblewords vector is completely unnecessary. What is it that you mean for it to represent?

 

[TheJokerV]

Is there a place where I can download your data files? Have you really estimated the runtime for your scenario to be a day? On what kind of hardware? It seems that you should be able to process this data about as fast as you can read it from disk; so if you can read at 30 megs per second from your drives, you should be able to eat up 825 megs in less than half a minute.

Well I'll try to put them up later if necessary but I will tell you this: They're made so that they won't finish in a reasonable amount of time using the naiive search. I have to make an algorithm so that it finishes in atleast 2 hours. Remeber the text file is just a bunch of random character's, they aren't seperated by spaces or anything so you have to test a wide amoutn/ lengths of strings. For instance: The string something, has 3 words in it some, thing, and something. I just want to make it work with a smaller text and dictionary file first.

I don't see where you find word breaks, for example. I also don't understand how you'll handle words like "it's" where an apostrophe appears; or hyphenated words.

There aren't words breaks. Just a test file of random chars and I have to find how many english words appear in the randomness. Also all the dictionary words are made up of lower case letters. If there's a hyphen, not a word.

As a style point, it looks like you've got lots of magic numbers foating around. It turns out you can use some standard functions for the character manipulation you're doing, and you can compare against character literals directly. For example, I'd rewrite this code: to use tolower() and 'a' and 'z' in place of 97 and 122.

You're completely correct on that, however I don't think that's the source of the error but i will rewrite the code segment.

I can't quite figure out your logic.

Let me please explain, As I'm sure you already, I'm trying to implement a trie search algorithm. SO there are 2 parts to this problem,
First I must make my trie. This counts as preprocessing and not runtime, runtime is the only thing that matters. So I first made my CTree class and generated the tree. I made a node called CTree and it has a variable that tells the user if it is the end of a word and a 26 element array that points to the next Tree node corresponding to the appropriate letter. For instance if I was trying to put the word and into the tree, I start with the top node which is declared as a global variable. Then I check to see if the "a" (nextchar[0]) branch of the tree tree node connected to another CTree. If so I return the pointer to that CTree so that the pointer may move down the tree. If not I create a new tree node and have the a branch of the current tree connect to the newly created node. The I return the value of the newly connected node so that the pointer may move down the tree. I do this for each char in the word. Once I reach the last char in the word I set the isword value of that correspond tree node to true to signify that this is indeed the end or a word and that the word count should increase.
Now in my actual searching algorithm I take in one character at a time from the text file. If the character is a letter it is potentially the beginning of a new word. So I put a new element in my vector starting form the top node and I loop through all the pointers in my vectors and have them go down the branch of their respective nodes corresponding to the letter that was read in. Now if the pointer get a non NULL value, it measn that it is still in the middle or end of a word. (it checks if the isword boolean is true the loop adds 1 to the wordcount) If the element of the vector (which contaisn the pointer moving through the tree) is NULL, it means that there are no more possible words so I delete the pointer from my vector. If the charcater read in is anything but a letter I delete all the elements of my vector(since a word can't contain anything but letters). That's basically it.

You don't mention if the error you get is at runtime or compile time, and you've not told us which tool set you're using on which operating system, so I'm a little in the dark with helping you out.

I'm using Visual Studio 2008 on Windows and it is a runtime error. The line I think is the problem is this segment:

if(*it == NULL){
						possiblewords.erase(it);
						it = possiblewords.begin();
					}

First the it=possiblewords.begin() isn't supposed to be there, its just something I used to debugging so talke that out but I think the problem has to do with erasing a element of the vector while iterating through it though I thought the iterator would compensate. EDIT: Now upon futher inspection I don't know what the problem is anymore.

which I can't quite understand. I'm not sure why you use the static_cast operator here. The CTree::isnext() member will return a pointer to a CTree object, not an iterator. The error doesn't seem to have anything to do with the return value being NULL; it's that you can't assign something to an iterator type that's not, itself, an iterator. You're trying to dereference the iterator to make it a type of the object that you're assigning to it, but that doesn't work either; the iterator can't be expected to iterate over arbitrary objects--particularly not those that aren't in an iteratable collection.

I use static cast because the is_next function takes in a character not a integer. I need to change the vsalue of the element the interator is going over. That's how they said to do it in my C++ text it isn't?

Mike thanks so much for your guidance man I really appreciate it.

 

[mikeblas]

Remeber the text file is just a bunch of random character's, they aren't seperated by spaces or anything so you have to test a wide amoutn/ lengths of strings.

Remember? This is the first time you've told us that.

There aren't words breaks. Just a test file of random chars and I have to find how many english words appear in the randomness.

Then this is a substantially different problem. You first said you have a large text file with an assortment of words; now you're saying they're words and just a stream of characters.

 

[TheJokerV]

Remember? This is the first time you've told us that.

Then this is a substantially different problem. You first said you have a large text file with an assortment of words; now you're saying there words and just a stream of characters.

I reread what I said and you're completely right and I am deeply apologetic. Anyway the characters are random and you basically have to find how many words are in the stream of characters.

 

[nameless_centurian]

how is your progress?

as a side note, i remembered this article (which admittedly isn't all that pertinent to your case) about some people from IBM (i believe..) that states that a Pentium IV can be expected to get about 200-400 Mbps throughput. I contacted the author a while back, and the numbers came from a citation of a paper that was written in about 1996. Disk interfaces have improved a little since then. memory interfaces have also improved. processing power has improved (especially if you consider multi-core technologies now!!). processor cache sizes have improved, too. these authors have at least two good articles on programming the cell processor in ddj.

I would think that if you can correctly code the aho-corasick tree to insert your dictionary, you should be able to run just about any string searches you want to in under 2 hours. your patterns and dictionary will have to be several gigabytes in order for it to run over 2 hours.