Skip to content

Instantly share code, notes, and snippets.

@josejuan
Created June 5, 2012 13:50
Show Gist options
  • Save josejuan/2875143 to your computer and use it in GitHub Desktop.
Save josejuan/2875143 to your computer and use it in GitHub Desktop.
Levenshtein subminimal test
<!DOCTYPE html>
<head>
<meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
<title>LevenshteinSubminimal test</title>
<style>
div {
float: left;
padding: 5px;
border-right: 1px solid gray;
}
i {
font-style: italic;
color: green;
background-color: #f0f0ff;
}
ul {
border-top: 1px solid gray;
}
</style>
<script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/jquery/1.7.2/jquery.min.js"></script>
<script type="text/javascript">
// Levenshtein(String, String) -> Integer
function Levenshtein(a, b) {
var n = a.length;
var m = b.length;
// matriz de cambios mínimos
var d = [];
// si una de las dos está vacía, la distancia es insertar todas las otras
if(n == 0)
return m;
if(m == 0)
return n;
// inicializamos el peor caso (insertar todas)
for(var i = 0; i <= n; i++)
(d[i] = [])[0] = i;
for(var j = 0; j <= m; j++)
d[0][j] = j;
// cada elemento de la matriz será la transición con menor coste
for(var i = 1, I = 0; i <= n; i++, I++)
for(var j = 1, J = 0; j <= m; j++, J++)
if(b[J] == a[I]) d[i][j] = d[I][J];
else d[i][j] = Math.min(d[I][j], d[i][J], d[I][J]) + 1;
// el menor número de operaciones
return d[n][m];
}
/*
LevenshteinSubminimal(String A, String B) -> {k: Integer, t: String}
A, es la cadena que introduce el usuario
B, es la cadena candidata a ser alternativa del usuario
k, es la mínima distancia Levenshtein de A sobre todas las subcadenas de B
t, es la cadena con menor distancia Levenshtein
*/
function LevenshteinSubminimal(A, B) {
var a = A.length;
var b = B.length;
// siempre comparamos A con las subcadenas de B
var f = function(s){return Levenshtein(A, s)}
// si A es mayor que B no comparamos subcadenas
if(a >= b)
return {k: f(B), t: B}
// peor caso y cotas
var m = {k: b+2, t: null}, c1 = a-1, c2 = a+1
for(var p = 0; p < b - c1; p++)
for(var l = c1, c3 = Math.min(c2, b - p); l <= c3; l++) {
var t = B.substr(p, l), k = f(t)
// mejor caso
if(m.k >= k)
m = {k: k, t: t}
}
return m
}
</script>
<script type="text/javascript">
$(function() {
$('input').keyup(function() {
var i = $(this);
var ul = i.parent().find('ul');
var s = i.val().toLowerCase();
var l = ul.find('li').map(function(){
var h = $(this).text().toLowerCase();
return {h: h, m: LevenshteinSubminimal(s, h)};
}).get();
// Array.Sort is a static member, must be accessible! (EMACScript 4th of course)
// http://www.ccs.neu.edu/home/dherman/browse/linux/es4/src/spec/library.pdf
l.sort(function(a, b) {
if(a.m.k < b.m.k || b.m.t == null) return -1
if(a.m.k > b.m.k || a.m.t == null) return 1
if(a.h.length < b.h.length) return -1
if(a.h.length > b.h.length) return 1
return 0
})
ul.html('<li>' + $(l).map(function() {
return this.h.replace(this.m.t, "<i title='" + this.m.k + "'>" + this.m.t + "</i>")
}).get().join('</li><li>') + '</li>')
});
});
</script>
</head>
<body>
<div>
Country list:<br />
<input type="text" />
<ul>
<li>Afghanistan</li>
<li>Åland Islands</li>
<li>Albania</li>
<li>Algeria</li>
<li>American Samoa</li>
<li>Andorra</li>
<li>Angola</li>
<li>Anguilla</li>
<li>Antigua and Barbuda</li>
<li>Argentina</li>
<li>Armenia</li>
<li>Aruba</li>
<li>Australia</li>
<li>Austria</li>
<li>Azerbaijan</li>
<li>Bahamas</li>
<li>Bahrain</li>
<li>Bangladesh</li>
<li>Barbados</li>
<li>Belarus</li>
<li>Belgium</li>
<li>Belize</li>
<li>Benin</li>
<li>Bermuda</li>
<li>Bhutan</li>
<li>Bolivia (Plurinational State of)</li>
<li>Bonaire, Saint Eustatius and Saba</li>
<li>Bosnia and Herzegovina</li>
<li>Botswana</li>
<li>Brazil</li>
<li>British Virgin Islands</li>
<li>Brunei Darussalam</li>
<li>Bulgaria</li>
<li>Burkina Faso</li>
<li>Burundi</li>
<li>Cambodia</li>
<li>Cameroon</li>
<li>Canada</li>
<li>Cape Verde</li>
<li>Cayman Islands</li>
<li>Central African Republic</li>
<li>Chad</li>
<li>Channel Islands</li>
<li>Chile</li>
<li>China</li>
<li>China, Hong Kong Special Administrative Region</li>
<li>China, Macao Special Administrative Region</li>
<li>Colombia</li>
<li>Comoros</li>
<li>Congo</li>
<li>Cook Islands</li>
<li>Costa Rica</li>
<li>Côte d'Ivoire</li>
<li>Croatia</li>
<li>Cuba</li>
<li>Curaçao</li>
<li>Cyprus</li>
<li>Czech Republic</li>
<li>Democratic People's Republic of Korea</li>
<li>Democratic Republic of the Congo</li>
<li>Denmark</li>
<li>Djibouti</li>
<li>Dominica</li>
<li>Dominican Republic</li>
<li>Ecuador</li>
<li>Egypt</li>
<li>El Salvador</li>
<li>Equatorial Guinea</li>
<li>Eritrea</li>
<li>Estonia</li>
<li>Ethiopia</li>
<li>Faeroe Islands</li>
<li>Falkland Islands (Malvinas)</li>
<li>Fiji</li>
<li>Finland</li>
<li>France</li>
<li>French Guiana</li>
<li>French Polynesia</li>
<li>Gabon</li>
<li>Gambia</li>
<li>Georgia</li>
<li>Germany</li>
<li>Ghana</li>
<li>Gibraltar</li>
<li>Greece</li>
<li>Greenland</li>
<li>Grenada</li>
<li>Guadeloupe</li>
<li>Guam</li>
<li>Guatemala</li>
<li>Guernsey</li>
<li>Guinea</li>
<li>Guinea-Bissau</li>
<li>Guyana</li>
<li>Haiti</li>
<li>Holy See</li>
<li>Honduras</li>
<li>Hungary</li>
<li>Iceland</li>
<li>India</li>
<li>Indonesia</li>
<li>Iran (Islamic Republic of)</li>
<li>Iraq</li>
<li>Ireland</li>
<li>Isle of Man</li>
<li>Israel</li>
<li>Italy</li>
<li>Jamaica</li>
<li>Japan</li>
<li>Jersey JEY</li>
<li>Jordan</li>
<li>Kazakhstan</li>
<li>Kenya</li>
<li>Kiribati</li>
<li>Kuwait</li>
<li>Kyrgyzstan</li>
<li>Lao People's Democratic Republic</li>
<li>Latvia</li>
<li>Lebanon</li>
<li>Lesotho</li>
<li>Liberia</li>
<li>Libya</li>
<li>Liechtenstein</li>
<li>Lithuania</li>
<li>Luxembourg</li>
<li>Madagascar</li>
<li>Malawi</li>
<li>Malaysia</li>
<li>Maldives</li>
<li>Mali</li>
<li>Malta</li>
<li>Marshall Islands</li>
<li>Martinique</li>
<li>Mauritania</li>
<li>Mauritius</li>
<li>Mayotte MYT</li>
<li>Mexico</li>
<li>Micronesia (Federated States of)</li>
<li>Monaco</li>
<li>Mongolia</li>
<li>Montenegro</li>
<li>Montserrat</li>
<li>Morocco</li>
<li>Mozambique</li>
<li>Myanmar</li>
<li>Namibia</li>
<li>Nauru</li>
<li>Nepal</li>
<li>Netherlands</li>
<li>New Caledonia</li>
<li>New Zealand</li>
<li>Nicaragua</li>
<li>Niger</li>
<li>Nigeria</li>
<li>Niue</li>
<li>Norfolk Island</li>
<li>Northern Mariana Islands</li>
<li>Norway</li>
<li>Occupied Palestinian Territory</li>
<li>Oman</li>
<li>Pakistan</li>
<li>Palau</li>
<li>Panama</li>
<li>Papua New Guinea</li>
<li>Paraguay</li>
<li>Peru</li>
<li>Philippines</li>
<li>Pitcairn</li>
<li>Poland</li>
<li>Portugal</li>
<li>Puerto Rico</li>
<li>Qatar</li>
<li>Republic of Korea</li>
<li>Republic of Moldova</li>
<li>Réunion</li>
<li>Romania</li>
<li>Russian Federation</li>
<li>Rwanda</li>
<li>Saint-Barthélemy</li>
<li>Saint Helena</li>
<li>Saint Kitts and Nevis</li>
<li>Saint Lucia</li>
<li>Saint-Martin (French part) MAF</li>
<li>Saint Pierre and Miquelon</li>
<li>Saint Vincent and the Grenadines</li>
<li>Samoa</li>
<li>San Marino</li>
<li>Sao Tome and Principe</li>
<li>Sark</li>
<li>Saudi Arabia</li>
<li>Senegal</li>
<li>Serbia</li>
<li>Seychelles</li>
<li>Sierra Leone</li>
<li>Singapore</li>
<li>Sint Maarten (Dutch part) SXM</li>
<li>Slovakia</li>
<li>Slovenia</li>
<li>Solomon Islands</li>
<li>Somalia</li>
<li>South Africa</li>
<li>South Sudan</li>
<li>Spain</li>
<li>Sri Lanka</li>
<li>Sudan</li>
<li>Suriname</li>
<li>Svalbard and Jan Mayen Islands</li>
<li>Swaziland</li>
<li>Sweden</li>
<li>Switzerland</li>
<li>Syrian Arab Republic</li>
<li>Tajikistan</li>
<li>Thailand</li>
<li>The former Yugoslav Republic of Macedonia</li>
<li>Timor-Leste</li>
<li>Togo</li>
<li>Tokelau</li>
<li>Tonga</li>
<li>Trinidad and Tobago</li>
<li>Tunisia</li>
<li>Turkey</li>
<li>Turkmenistan</li>
<li>Turks and Caicos Islands</li>
<li>Tuvalu</li>
<li>Uganda</li>
<li>Ukraine</li>
<li>United Arab Emirates</li>
<li>United Kingdom of Great Britain and Northern Ireland</li>
<li>United Republic of Tanzania</li>
<li>United States of America</li>
<li>United States Virgin Islands</li>
<li>Uruguay</li>
<li>Uzbekistan</li>
<li>Vanuatu</li>
<li>Venezuela (Bolivarian Republic of)</li>
<li>Viet Nam</li>
<li>Wallis and Futuna Islands</li>
<li>Western Sahara</li>
<li>Yemen</li>
<li>Zambia</li>
<li>Zimbabwe</li>
</ul>
</div>
<div>
Fruits list:<br />
<input type="text" />
<ul>
<li>Abiu</li>
<li>Acai</li>
<li>Acerola</li>
<li>Ackee</li>
<li>African Cherry Orange</li>
<li>Alligator apple</li>
<li>Amazon grape</li>
<li>Ambarella</li>
<li>American Mayapple</li>
<li>Apple</li>
<li>Apricot</li>
<li>Araza</li>
<li>Arhat</li>
<li>Avocado</li>
<li>Babaco</li>
<li>Bael</li>
<li>Banana</li>
<li>Barbadine</li>
<li>Barbados cherry</li>
<li>Barberry</li>
<li>Bayberry</li>
<li>Beach plum</li>
<li>Bearberry</li>
<li>Beechnut</li>
<li>Berry</li>
<li>Betel nut</li>
<li>Bignay</li>
<li>Bilberry</li>
<li>Bilimbi</li>
<li>Bitter gourd</li>
<li>Black apple</li>
<li>Black cherry</li>
<li>Black mulberry</li>
<li>Black raspberry</li>
<li>Black sapote</li>
<li>Blackberry</li>
<li>Blackcurrant</li>
<li>Blood orange</li>
<li>Blue tongue</li>
<li>Blueberry</li>
<li>Bolwarra</li>
<li>Bottle gourd</li>
<li>Boysenberry</li>
<li>Bramble</li>
<li>Brazil nut</li>
<li>Breadfruit</li>
<li>Broadleaf Bramble</li>
<li>Buffaloberry</li>
<li>Burdekin plum</li>
<li>Burmese grape</li>
<li>Cacao</li>
<li>Caimito</li>
<li>Cajamanga</li>
<li>Calabashtree</li>
<li>Camucamu</li>
<li>Canistel</li>
<li>Cantaloupe</li>
<li>Cape gooseberry</li>
<li>Carambola</li>
<li>Cardon</li>
<li>Carob</li>
<li>Cashew</li>
<li>Cedar Bay Cherry</li>
<li>Cempedak</li>
<li>Ceylon gooseberry</li>
<li>Che</li>
<li>Chenet</li>
<li>Cherimoya</li>
<li>Cherry</li>
<li>Chinese bayberry</li>
<li>Chinese mulberry</li>
<li>Chokeberry</li>
<li>Citron</li>
<li>Clementine</li>
<li>Cloudberry</li>
<li>Cluster fig</li>
<li>Coconut</li>
<li>Cocoplum</li>
<li>Coffee</li>
<li>Common apple-berry</li>
<li>Conkerberry</li>
<li>Cornelian Cherry</li>
<li>Crabapple</li>
<li>Cranberry</li>
<li>Crowberry</li>
<li>Cudrang</li>
<li>Cudrania</li>
<li>Cupuacu</li>
<li>Currant</li>
<li>Custard apple</li>
<li>Damson</li>
<li>Date</li>
<li>Date palm</li>
<li>Date-plum</li>
<li>Davidson's plum</li>
<li>Desert fig</li>
<li>Desert lime</li>
<li>Dewberry</li>
<li>Doubah</li>
<li>Dragonfruit</li>
<li>Durain</li>
<li>Eastern May Hawthorn</li>
<li>Eggfruit</li>
<li>Eggplant</li>
<li>Elderberry</li>
<li>Elephant apple</li>
<li>Emblic</li>
<li>Emu apple</li>
<li>Entawak</li>
<li>Etrog</li>
<li>Feijoa</li>
<li>Fibrous satinash</li>
<li>Fig</li>
<li>Fiji longan</li>
<li>Finger lime</li>
<li>Galendar</li>
<li>Galia</li>
<li>Gandaria</li>
<li>Genip</li>
<li>Genipap</li>
<li>Giant Granadilla</li>
<li>Golden apple</li>
<li>Gooseberry</li>
<li>Goumi</li>
<li>Gourds</li>
<li>Grape</li>
<li>Grapefruit</li>
<li>Grapple</li>
<li>Greengage</li>
<li>Grenadilla</li>
<li>Guanabana</li>
<li>Guarana</li>
<li>Guava</li>
<li>Guavaberry</li>
<li>Hackberry</li>
<li>Hardy kiwi</li>
<li>Hawthorn</li>
<li>Hog plum</li>
<li>Honeycrisp Apple</li>
<li>Honeydew melon</li>
<li>Honeysuckle</li>
<li>Horned melon</li>
<li>Huckleberry</li>
<li>Huito</li>
<li>Illawarra plum</li>
<li>Indian almond</li>
<li>Indian fig</li>
<li>Indian jujube</li>
<li>Indian prune</li>
<li>Indian strawberry</li>
<li>Ita Palm</li>
<li>Jaboticaba</li>
<li>Jackfruit</li>
<li>Jagua</li>
<li>Jamaica Cherry</li>
<li>Jambul</li>
<li>Japanese Bayberry</li>
<li>Japanese raisin</li>
<li>Jasmine</li>
<li>Jatoba</li>
<li>Jenipapo</li>
<li>Jocote</li>
<li>Jujube</li>
<li>June plum</li>
<li>Kaffir lime</li>
<li>Kahikatea</li>
<li>Kakadu lime</li>
<li>Kakadu plum</li>
<li>Kandis fruit</li>
<li>Karkalla</li>
<li>Keppel fruit</li>
<li>Key lime</li>
<li>Kiwi</li>
<li>Kumquat</li>
<li>Kundong</li>
<li>Kutjera</li>
<li>Lablab</li>
<li>Lady apple</li>
<li>Langsat</li>
<li>Lanzones</li>
<li>Lapsi</li>
<li>Legume</li>
<li>Lemon</li>
<li>Lemon aspen</li>
<li>Leucaena</li>
<li>Lillipilli</li>
<li>Lilly Pilly</li>
<li>Lime</li>
<li>Lingonberry</li>
<li>Loganberry</li>
<li>Longan</li>
<li>Loquat</li>
<li>Lucuma</li>
<li>Lulo</li>
<li>Lychee</li>
<li>Mabolo</li>
<li>Macadamia</li>
<li>Malay apple</li>
<li>Mamey sapote</li>
<li>Mamoncillo</li>
<li>Mandarin</li>
<li>Mango</li>
<li>Mangosteen</li>
<li>Manila tamarind</li>
<li>Manoao</li>
<li>Marang</li>
<li>Mayapple</li>
<li>Mayhaw</li>
<li>Maypop</li>
<li>Medlar</li>
<li>Melinjo</li>
<li>Melon</li>
<li>Melon pear</li>
<li>Midyim</li>
<li>Mock buckthorn</li>
<li>Mock strawberry</li>
<li>Monkey apple</li>
<li>Monstera</li>
<li>Morinda</li>
<li>Mountain soursop</li>
<li>Mulberry</li>
<li>Mundu</li>
<li>Muntries</li>
<li>Muskmelons</li>
<li>Myrtle</li>
<li>Nageia</li>
<li>Nance</li>
<li>Nannyberry</li>
<li>Naranja</li>
<li>Naranjilla</li>
<li>Native cherry</li>
<li>Native currant</li>
<li>Native gooseberry</li>
<li>Nectarine</li>
<li>Neem</li>
<li>Nungu</li>
<li>Nutmeg</li>
<li>Oil palm</li>
<li>Olallieberry</li>
<li>Old World Sycomore</li>
<li>Olive</li>
<li>Orange</li>
<li>Orangelo</li>
<li>Oregon grape</li>
<li>Otaheite apple</li>
<li>Papaya</li>
<li>Passion fruit</li>
<li>Pawpaw</li>
<li>Peach</li>
<li>Peanut</li>
<li>Pear</li>
<li>Pequi</li>
<li>Persimmon</li>
<li>Pewa</li>
<li>Pigeon Plum</li>
<li>Pigface</li>
<li>Pili nut</li>
<li>Pineapple</li>
<li>Pitaya</li>
<li>Pitomba</li>
<li>Plantain</li>
<li>Plum</li>
<li>Podocarpus</li>
<li>Poha</li>
<li>Pois doux</li>
<li>Pomcite</li>
<li>Pomegranate</li>
<li>Pomelo</li>
<li>Pommecythere</li>
<li>Pommerac</li>
<li>Pond apple</li>
<li>Prickly Pear</li>
<li>Prumnopitys</li>
<li>Prune</li>
<li>Pulasan</li>
<li>Pummelo</li>
<li>Pumpkin</li>
<li>Pupunha</li>
<li>Purple apple-berry</li>
<li>Quandong</li>
<li>Quenepa</li>
<li>Quince</li>
<li>Raisin</li>
<li>Rambutan</li>
<li>Rangpur</li>
<li>Raspberry</li>
<li>Red bayberry</li>
<li>Red mombin</li>
<li>Red mulberry</li>
<li>Redcurrant</li>
<li>Rhubarb</li>
<li>Riberry</li>
<li>Ridged gourd</li>
<li>Rimu</li>
<li>Rose apple</li>
<li>Rose hip</li>
<li>Rose myrtle</li>
<li>Rose-leaf bramble</li>
<li>Rowan</li>
<li>Sageretia</li>
<li>Saguaro</li>
<li>Salak</li>
<li>Salal berry</li>
<li>Salmonberry</li>
<li>Sandpaper fig</li>
<li>Santol</li>
<li>Sapodilla</li>
<li>Sapote</li>
<li>Saskatoon</li>
<li>Saskatoonberry</li>
<li>Satsuma</li>
<li>Sea grape</li>
<li>Sea-buckthorn</li>
<li>Serviceberry</li>
<li>Shipova</li>
<li>Silkworm thorn</li>
<li>Snow berry</li>
<li>Soncoya</li>
<li>Soursop</li>
<li>Star apple</li>
<li>Strawberry</li>
<li>Strawberry-guava</li>
<li>Strawberry-pear</li>
<li>Sugar apple</li>
<li>Surinam cherry</li>
<li>Sweet apple-berry</li>
<li>Sweet lemon</li>
<li>Sweetsop</li>
<li>Sycamore fig</li>
<li>Sycomore</li>
<li>Tamarillo</li>
<li>Tamarind</li>
<li>Tangelo</li>
<li>Tangerine</li>
<li>Tanjong</li>
<li>Taxus baccata</li>
<li>Texas persimmon</li>
<li>Thimbleberry</li>
<li>Tomato</li>
<li>Toyon</li>
<li>Ugli fruit</li>
<li>Ugn</li>
<li>Uva (grape)</li>
<li>Vanilla</li>
<li>Velvet Tamarind</li>
<li>Voavanga</li>
<li>Water Apple</li>
<li>Watermelon</li>
<li>Wax Apple</li>
<li>Wax gourd</li>
<li>White aspen</li>
<li>White mulberry</li>
<li>White sapote</li>
<li>Wild orange</li>
<li>Wineberry</li>
<li>Winter melon</li>
<li>Wolfberry</li>
<li>Wongi</li>
<li>Wood Apple</li>
<li>Xigua</li>
<li>Xylocarp</li>
<li>Yali pears</li>
<li>Yamamomo</li>
<li>Yangmei</li>
<li>Yellow plum</li>
<li>Yumberry</li>
<li>Zhe</li>
<li>Zigzag vine</li>
<li>Ziziphus</li>
<li>Zucchini</li>
</ul>
</div>
<div>
Actors list:<br />
<input type="text" />
<ul>
<li>Adam Sandler</li>
<li>Adrien Brody</li>
<li>Al Pacino</li>
<li>Angelina Jolie</li>
<li>Anne Hathaway</li>
<li>Arnold Schwarzenegger</li>
<li>Audrey Tautou</li>
<li>Bette Davis</li>
<li>Bill Murray</li>
<li>Brad Pitt</li>
<li>Burt Reynolds</li>
<li>Cameron Diaz</li>
<li>Cate Blanchett</li>
<li>Catherine Zeta-Jones</li>
<li>Charlize Theron</li>
<li>Chevy Chase</li>
<li>Chuck Norris</li>
<li>Drew Barrymore</li>
<li>Dustin Hoffman</li>
<li>Edward Norton</li>
<li>Elizabeth Taylor</li>
<li>Emma Watson</li>
<li>George Clooney</li>
<li>Gwyneth Paltrow</li>
<li>Halle Berry</li>
<li>Heath Ledger</li>
<li>Hilary Swank</li>
<li>Jack Nicholson</li>
<li>James Stewart</li>
<li>Jennifer Aniston</li>
<li>Joan Crawford</li>
<li>Joaquin Phoenix</li>
<li>Jodie Foster</li>
<li>Johnny Depp</li>
<li>Julia Roberts</li>
<li>Kate Winslet</li>
<li>Katie Holmes</li>
<li>Kristen Stewart</li>
<li>Laurence Olivier</li>
<li>Leonardo DiCaprio</li>
<li>Marilyn Monroe</li>
<li>Mark Wahlberg</li>
<li>Marlon Brando</li>
<li>Matt Damon</li>
<li>Meryl Streep</li>
<li>Mischa Barton</li>
<li>Morgan Freeman</li>
<li>Nicole Kidman</li>
<li>Oliver Reed</li>
<li>Penelope Cruz</li>
<li>Reese Witherspoon</li>
<li>Richard Gere</li>
<li>Robin Williams</li>
<li>Russell Crowe</li>
<li>Sandra Bullock</li>
<li>Shirley MacLaine</li>
<li>Sylvester Stallone</li>
<li>Tom Cruise</li>
<li>Tom Hanks</li>
<li>Uma Thurman</li>
<li>Warren Beatty</li>
<li>Will Smith</li>
<li>Woody Allen</li>
<li>Zac Efron</li>
</ul>
</div>
</body>
</html>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment