|
Way, way too long ago I worked for a state DMV and they used something called the "Soundex Code" to hash surnames into 5-character alpha-num strings. Similar-sounding names cluster about the same hash values.
U can find the algorithm on wiki.
Tadeusz Westawic
An ounce of Clever is worth a pound of Experience.
|
|
|
|
|
|
Padmanabha_M wrote: i dont want to use new libraries.
Use the old libraries.
"Republicans are the party that says government doesn't work and then they get elected and prove it." -- P.J. O'Rourke I'm a proud denizen of the Real Soapbox[ ^] ACCEPT NO SUBSTITUTES!!!
|
|
|
|
|
plz help for me to do an project on image segmentation.
plz send me the alogorithm and the techniques used for image segmentation
with s very useful to me.
i need it at most the earlier to do this.
Thanking you,
Sridhar.
|
|
|
|
|
I suggest you read this article http://en.wikipedia.org/wiki/Segmentation_(image_processing)[^] then decide what you want to do, then write some code to do it, then,if you have problems with the code, post on the appropriate language forum.
Regards
David R
---------------------------------------------------------------
"Every program eventually becomes rococo, and then rubble." - Alan Perlis
|
|
|
|
|
Hello
Im doing K-means clustering and am about to implement the Mahalanobis distance. I have a problem with sometimes the matrix is singular. Im not really sure what it means in this case and what to do about it? Im fairly sure that my code is ok, but here is the code for calculating the covariance matrix:
public static Matrix CovarianceMatrix(List<double[]> dataset)
{
double[] means = new double[dataset[0].Length];
Matrix cov = new Matrix(dataset[0].Length, dataset[0].Length);
double sum = 0;
for (int i = 0; i < dataset[0].Length; i++)
{
for (int j = 0; j < dataset.Count; j++)
{
means[i] += dataset[j][i];
}
means[i] /= dataset.Count;
}
double[,] subresults = new double[dataset[0].Length, dataset.Count];
for (int j = 0; j < dataset.Count; j++)
{
for (int i = 0; i < dataset[0].Length; i++)
{
subresults[i, j] = dataset[j][i] - means[i];
}
}
for (int i = 0; i < dataset[0].Length; i++)
{
for (int j = i; j < dataset[0].Length; j++)
{
double s = 0;
for (int x = 0; x < dataset.Count; x++)
{
s += subresults[i, x] * subresults[j, x];
}
cov.SetElement(i, j, s / dataset.Count);
if (i != j) cov.SetElement(j, i, s / dataset.Count);
}
}
return cov;
}
And here for the distance:
public static double Mahalanobis(double[] vector1, double[] vector2, Matrix covariance)
{
Matrix v1 = new Matrix(vector1, vector1.Length);
Matrix v2 = new Matrix(vector2, vector2.Length);
Matrix m = v1.Subtract(v2);
return (double)(m.Transpose()).Multiply(covariance.Inverse()).Multiply(m).GetElement(0, 0);
}
If more information (or comments), or a working code sample is perfered, let me know. However, some times it can cluster without problem, so I think it is more about how to handle the singularity than the code it self.
Looking forward to hear from you
modified on Friday, May 22, 2009 5:32 AM
|
|
|
|
|
A singular matrix has a determinant of zero. That means you can't invert it.
That's probably happening when you're inverting your covariance matrix: covariance.Inverse()
It also means that your covariance matrix isn't positive semi-definite and therefore it's not invertable. So the vectors you are seding to the Mahalanobis function are probably linear combinations of one another.
If these are random vectors, it could be that a component of the vector is extraneous. Better check your vectors.
|
|
|
|
|
I am looking for code in C# or in Matlab that can represent the shape using -- Region based shape representation-- and calculate the similarity between two shapes
|
|
|
|
|
Hi.
I have a text file full of words (lets say one word per line).
I want to find all words starting with a given pattern.
What's the best algorithm to do this?
Thanks,
vSoares
|
|
|
|
|
vSoares wrote: What's the best algorithm to do this?
well, what is your definition of best? best matches? best execution time? best ...?
there are plenlenty of algorithms out them, did you try exact string match[^] or this[^]
|
|
|
|
|
Yes, I tried but i was expecting someone who had some experience with this kind of algorithms to point me in the right direction.
I agree, "best" is very broad. I need a fast search algorithm. I can optimize the source if needed.
It's not an exact string match. It's all strings beggining with a given pattern, something like google suggestions.
vSoares
|
|
|
|
|
Tries and related data structures come to mind, as well as the bitap algorithm
Just general suggestions..
|
|
|
|
|
vSoares wrote: I need a fast search algorithm. I can optimize the source if needed.
Sort the file then use a binary search?
Regards
David R
---------------------------------------------------------------
"Every program eventually becomes rococo, and then rubble." - Alan Perlis
|
|
|
|
|
Load them into a database and use SQL.
|
|
|
|
|
I think I would give it a try with regex.
If you really want to program something nice, then maybe suffix trees are good.
Cheers
You have the thought that modern physics just relay on assumptions, that somehow depends on a smile of a cat, which isn’t there.( Albert Einstein)
|
|
|
|
|
Hi...
This is graphics related.I need to draw a map .I have the lat long values of it .I was able to map these to screen coordinates and then draw the map.The problem i need help with is how do i do the reverse.For the initial case its simple,just rearrangement of window to view port mapping formula .i.e.,
u = (x-xmin)* sx+ umin
v = (y-ymin)* sy + vmin
But once the zoom and pan operations are applied on the map, I dont know how to get the latitude longitude values from the screen coordinate point.
If some one knows how to solve this ,Please help me
Thanks in advance
|
|
|
|
|
You must use the zoom and pan factors in the equation to get map coordinates from screen coordinates: pan will be an x-y offset, while zoom will be a multiplication/division constant.
Note that you might introduce a conversion error if zoom is a floating point number, so you might consider using an integer. The same of course goes for pan factors.
Hope this can help.
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
Hi,
u = (x-xmin)* sx + umin
v = (y-ymin)* sy + vmin
are formulas to translate and scale a coordinate system (x,y) to a new system (u,v)
The inverse operation has exactly the same structure: swap every u and x, and every y and v, and you become the inverse formulas.
x = (u-umin)* su + xmin
y = (v-vmin)* sb + ymin
All you need now is the new constants
Substituting one set into the other should lead to two identity relations, hence:
su=1/sx and sv=1/sy
Luc Pattyn [Forum Guidelines] [My Articles]
The quality and detail of your question reflects on the effectiveness of the help you are likely to get.
Show formatted code inside PRE tags, and give clear symptoms when describing a problem.
|
|
|
|
|
How would I calculate the Z Scores for a list of data - for example if I run a selection on the database then tabulate the values from a particular variable (Marital Status, for example) I get the following columns:
A Description - Widowed, Married, Divorced etc.
Universe - The number of people in the database with that value
Selection - The number of people in the selection with that value
Universe % - the percentage of the total people on the database who have that value
Selection % - the percentage of the total people on the selection who have that value
I also have the number of people on the database and the number of people in the selection
Is it possible to work out a Z Score for each line in this list given the above information and how would I do it in C#?
Thanks
|
|
|
|
|
If think this[^] is what you're looking for.
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
Hello,
I have an app that searches for a directory that has the format "LastName FirstName". However, I want to account for misspellings in the name that is entered. For instance, the directory is named "Stein" but the user enters "Stien". Of course, more un-common misspellings are also possible. I'm looking into using NetSpell[^] and defining a custom dictionary based on the directory names. However, since new directories are always being added with different names, I was wondering what the best way is to automatically keep this dictionary up-to-date. I can certainly auto-update when the program is started, but I'd like a way to keep it updated without have to restart the program. Any ideas?
Thanks,
Dybs
|
|
|
|
|
Hi,
you could have it work like this:
1.
on app start, scan the directory for names; for each name, generate all reasonable variations and add them to a list (variations could be: dropping a letter, swapping two consecutive letters, ...)
2.
whatever the user enters, compare against the list of exact and almost-exact names, and warn the user if there is either no match at all or ambiguity, i.e. he entered something that could lead to different hits.
3.
install a FileSystemWatcher to detect creation of new file objects, treat them the same way as under 1.
Luc Pattyn [Forum Guidelines] [My Articles]
The quality and detail of your question reflects on the effectiveness of the help you are likely to get.
Show formatted code inside PRE tags, and give clear symptoms when describing a problem.
|
|
|
|
|
Thanks for the suggestions. I completely forgot about the FileSystemWatcher class Never used it before, but it's exactly what I need. What I was originally thinking was on app start, build a dictionary in NetSpell of all the directory names I'd be searching. If a user enters a directory that doesn't exist, it would run that name through NetSpell and search for any directories matching its suggestions (rather than generating all the variations myself - there are several hundred directories, and that could take some time). But the SoundEx algorithm Henry suggested below sounds like it might be useful as well. Thanks again!
Dybs
|
|
|
|
|
you're welcome.
Luc Pattyn [Forum Guidelines] [My Articles]
The quality and detail of your question reflects on the effectiveness of the help you are likely to get.
Show formatted code inside PRE tags, and give clear symptoms when describing a problem.
|
|
|
|
|
As part of 1. from Lucs' solution a Soundex algorithm might prove useful. There is A SoundEx implementation in .NET[^] on CP that might help.
Henry Minute
Do not read medical books! You could die of a misprint. - Mark Twain
Girl: (staring) "Why do you need an icy cucumber?"
“I want to report a fraud. The government is lying to us all.”
|
|
|
|