algorithm - Finding groups of similar strings in a large set of strings -

-

i have reasonably large set of strings (say 100) has number of subgroups characterised similarity. trying find/design algorithm find theses groups reasonably efficiently.

as example let's input list on left below, , output groups on right.

input                           output -----------------               ----------------- jane doe                        mr philip roberts mr philip roberts               phil roberts      foo mcbar                       philip roberts    david jones                      phil roberts                    foo mcbar         davey jones            =>          john smith                      david jones       philip roberts                  dave jones        dave jones                      davey jones       jonny smith                                                      jane doe                                           john smith                                        jonny smith

does know of ways solve reasonably efficiently?

the standard method finding similar strings seems levenshtein distance, can't see how can make use of here without having compare every string every other string in list, , somehow decide on difference threshold deciding if 2 strings in same group or not.

an alternative algorithm hashes strings down integer, similar strings hash integers close on number-line. have no idea algorithm though, if 1 exists

does have thoughts/pointers?

update: @will a: perhaps names weren't example first thought. starting point think can assume in data working with, small change in string not make jump 1 group another.

another popular method associate strings jaccard index. start http://en.wikipedia.org/wiki/jaccard_index.

here's article using jaccard-index (and couple of other methods) solve problem yours:

http://matpalm.com/resemblance/


Comments

Post a Comment

Popular posts from this blog

c++ - How do I get a multi line tooltip in MFC -

-
right now, have tool tip pops when hover on edit box. problem tool tip contains multiple error messages , in 1 long line. need have each error message on own line. error messages contained in cstring new line seperating them. my existing code below. bool ontooltiptext(uint, nmhdr* pnmhdr, lresult* presult) { assert(pnmhdr->code == ttn_needtexta || pnmhdr->code == ttn_needtextw); // need handle both ansi , unicode versions of message tooltiptexta* pttta = (tooltiptexta*)pnmhdr; tooltiptextw* ptttw = (tooltiptextw*)pnmhdr; // tchar szfulltext[256]; cstring strtiptext=_t(""); uint nid = pnmhdr->idfrom; if (pnmhdr->code == ttn_needtexta && (pttta->uflags & ttf_idishwnd) || pnmhdr->code == ttn_needtextw && (ptttw->uflags & ttf_idishwnd)) { // idfrom hwnd of tool nid = ::getdlgctrlid((hwnd)nid); } //m_errprojaccel[ch] contains 1 or more error messages each...
Read more

asp.net - In javascript how to find the height and width -

-
i having .aspx , masterpage page. in masterpage loading aspx page . in aspx page design using generating table structure using code-behind server in javascript how find height , width . regards, kumar if you're looking table height , width, should it var tbl = document.getelementbyid('tbldemo'); alert(tbl.offsetwidth + '\n' + tbl.offsetheight);
Read more

c# - DataTable to EnumerableRowCollection -

-
i have datatable according client requirement can contain invalid date "00/00/1999",null,empty string.(typed datset) when collect them enumerables wish convert of invalid forms empty string. (i.e) enumerablerowcollection<datarow> query = order in _table.asenumerable() select new { orderdate= string.isnullorempty(convert.tostring(order.field<datetime>("orderdate")) || (how check date invalid date) ? string.empty : order.field<datetime>("orderdate") } how check whether date valid date or not? datetime.tryparse...like given current code: datetime date; enumerablerowcollection<datarow> query = order in _table.asenumerable() select new { orderdate= string.isnullorempty(convert.tostring(order.field<datetime>("orderdate")) || !datetime.tryparse(convert.tostring(order.field<datetime...
Read more