spellchecker/bktree.cpp at master · pankaj-a/spellchecker · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<iostream>
#include<algorithm>
#include<set>
#include<fstream>
#include<string.h>
#include<map>
#include<vector>
#include "bktree.h"
#include<math.h>
#include "levenshtein.h"

using namespace std;


node* createnode(string s,long long int cnt)
{
	node *temp=new node;
	temp->value=s;
	temp->freq=cnt;
	temp->children=NULL;
	return temp;
}

/*char filterNonAlphabetic(char& letter) {
	if (isalpha(letter)) { return tolower(letter); }
	return '-';
}*/

bool insert(node *root,node *cur)
{
	if(cur==NULL)
	{
		cout<<"Null node insertion not possible\n";
		return false;
	}
	int d=DynamicLevenshtein(root->value,cur->value);
	//cout<<d<<endl;
	if(d==0)
	{
		//cout<<"already exists\n";
		return false;
	}
	if(!root->children)
	{
		root->children=new map<int,node*>();
		root->children->insert(make_pair(d,cur));
	}
	else
	{
		map<int,node*>::iterator it=root->children->find(d);
		if(it==root->children->end())
		{
			root->children->insert(make_pair(d,cur));
			return true;
		}
		insert(it->second,cur);
	}
}
void GenerateResult(node *root,string x,int tolerance,map<unsigned long long int,string >&result,set<string>&result_strings)
{
	int dis=DynamicLevenshtein(root->value,x);
	//cout<<root->value<<endl;
	//if(dis==0){cout<<root->value<<"\n\n";//return 0;
	//		return 0;}


	if(dis<=tolerance)
	{
		//cout<<root->value<<'\n';
		result_strings.insert(root->value);
		result.insert(make_pair((unsigned long long int)(root->freq*pow(1000,tolerance-dis)),root->value));
	}
	if(root->children!=NULL)
	{
		for(map<int,node*>::iterator it=root->children->begin();it!=root->children->end();++it)
		{
			if(dis-tolerance<=it->first && dis+tolerance>=it->first)
			{	//cout<<it->second->value<<endl;
				GenerateResult(it->second,x,tolerance,result,result_strings);
				}
		}
	}
}
/*node* LoadFromFile(const string& filename)
{
	node *root=NULL;
	string x;
	ifstream file(filename.c_str(), ios_base::binary | ios_base::in);
	file.seekg(0, ios_base::end);
	int length = file.tellg();
	file.seekg(0, ios_base::beg);
	string line(length, '0');
	file.read(&line[0], length);
	transform(line.begin(), line.end(), line.begin(), filterNonAlphabetic);
	string::size_type end = line.size();
	//cout<<line;
	for (string::size_type i = 0;;)
	{
		while (line[++i] == '-' && i < end); //find first '-' character
		if (i >= end) { break; }
		string::size_type begin = i;
		while (line[++i] != '-' && i < end); //find first not of '-' character
		x=line.substr(begin, i - begin);
		if(root==NULL)root=createnode(x);
		else insert(root,createnode(x));
	}
	cout<<"Dictionary loaded successfully\n";
	return root;
}*/
node* LoadFromFile(const string& filename)
{
	node *root=NULL;
	string x;
	long long int cnt;
	ifstream ifile(filename.c_str());
	while(ifile)
	{
		ifile>>x;
		ifile>>cnt;
		//cout<<x<<' '<<cnt<<endl;
		if(root==NULL)root=createnode(x,cnt);
		else insert(root,createnode(x,cnt));
	}
	cout<<"Dictionary loaded successfully\n";
	return root;
}