123:
349:
38:
1891:
107:
333:
2350:
887:
For example, consider the same 3-bit code consisting of the two codewords "000" and "111". The
Hamming space consists of 8 words 000, 001, 010, 011, 100, 101, 110 and 111. The codeword "000" and the single bit error words "001","010","100" are all less than or equal to the Hamming distance of 1 to
1562:
function will compute the
Hamming distance of two integers (considered as binary values, that is, as sequences of bits). The running time of this procedure is proportional to the Hamming distance rather than to the number of bits in the inputs. It computes the
888:"000". Likewise, codeword "111" and its single bit error words "110","101" and "011" are all within 1 Hamming distance of the original "111". In this code, a single bit error is always within 1 Hamming distance of the original codes, and the code can be
1402:
objects) of equal length by creating a sequence of
Boolean values indicating mismatches and matches between corresponding positions in the two inputs, then summing the sequence with True and False values, interpreted as one and zero, respectively.
2354:
823:=2 error detecting. This means that if one bit is flipped or two bits are flipped, the error can be detected. If three bits are flipped, then "000" becomes "111" and the error cannot be detected.
2192:
Jarrous, Ayman; Pinkas, Benny (2009). "Secure
Hamming Distance Based Computation and Its Applications". In Abdalla, Michel; Pointcheval, David; Fouque, Pierre-Alain; Vergnaud, Damien (eds.).
1148:
However, for comparing strings of different lengths, or strings where not just substitutions but also insertions or deletions have to be expected, a more sophisticated metric like the
1116:
1081:
756:
896:. Since the Hamming distance between "000" and "111" is 3, and those comprise the entire set of codewords in the code, the minimum Hamming distance is 3, which satisfies
580:), as it fulfills the conditions of non-negativity, symmetry, the Hamming distance of two words is 0 if and only if the two words are identical, and it satisfies the
320:
280:
240:
200:
1046:
1020:
1136:
2705:
2600:
2639:
2565:
2570:
819:
For example, consider a code consisting of two codewords "000" and "111". The
Hamming distance between these two words is 3, and therefore it is
688:
for an appropriate choice of the â operator, much as the difference between two integers can be seen as a distance from zero on the number line.
437:
The
Hamming distance between two equal-length strings of symbols is the number of positions at which the corresponding symbols are different.
2575:
2269:
2240:
2211:
2175:
2108:
2073:
2038:
1995:
59:
2560:
2786:
2654:
2595:
2467:
2436:
81:
2502:
1909:
2232:
964:
to count the number of flipped bits in a fixed-length binary word as an estimate of error, and therefore is sometimes called the
2365:
2682:
2359:
798:
445:
The symbols may be letters, bits, or decimal digits, among other possibilities. For example, the
Hamming distance between:
1395:
569:
2687:
2542:
398:
that could have transformed one string into the other. In a more general context, the
Hamming distance is one of several
1954:
286:
246:
206:
166:
2766:
2492:
2616:
758:
by treating each symbol in the string as a real coordinate; with this embedding, the strings form the vertices of an
52:
46:
2771:
2649:
2552:
2428:
2261:
2522:
1934:
2781:
2677:
2621:
2476:
2387:
1959:
383:
159:
2580:
63:
2827:
2776:
2512:
1559:
981:
1743:) assembly instruction. Certain compilers such as GCC and Clang make it available via an intrinsic function:
2817:
2725:
2065:
1086:
1051:
993:
812:
error detecting if, and only if, the minimum
Hamming distance between any two of its codewords is at least
348:
122:
2822:
2730:
2672:
2532:
2460:
2092:
1890:
732:
2537:
2196:. Lecture Notes in Computer Science. Vol. 5536. Berlin, Heidelberg: Springer. pp. 107â124.
1944:
1939:
1149:
802:
565:
368:
The minimum distance between any two vertices is the
Hamming distance between the two binary strings.
2735:
2124:
2055:
1919:
581:
2664:
2631:
2418:
2406:
2167:
1914:
1896:
989:
946:
871:
866:-errors correcting if the minimum Hamming distance between any two of its codewords is at least 2
767:
375:
332:
106:
1450:"""Return the Hamming distance between equal-length sequences."""
1160:
The following function, written in Python 3, returns the Hamming distance between two strings:
2796:
2432:
2326:
2308:
2265:
2236:
2207:
2159:
2104:
2069:
2034:
2030:
1991:
1985:
1949:
1564:
961:
2791:
2761:
2715:
2453:
2422:
2396:
2316:
2298:
2197:
2149:
2139:
289:
1578:
that repeatedly finds and clears the lowest-order nonzero bit. Some compilers support the
2644:
2585:
2497:
934:
722:
407:
296:
256:
249:
216:
209:
176:
169:
1025:
999:
1582:
function which can calculate this using specialized processor hardware where available.
2832:
2697:
2590:
2321:
2286:
2144:
2061:
1904:
1579:
1571:
1552:
1121:
917:
880:
700:
677:
2811:
2507:
2484:
1929:
950:
794:
577:
414:
403:
399:
394:
required to change one string into the other, or equivalently, the minimum number of
149:
2410:
2171:
1207:"""Return the Hamming distance between two strings."""
945:, in 1950. Hamming weight analysis of bits is used in several disciplines including
2710:
2527:
2378:
2369:
1567:
985:
954:
938:
721:; it is equivalent as a metric space to the set of distances between vertices in a
707:
426:
422:
2303:
386:
or vectors of equal length is the number of positions at which the corresponding
2720:
2202:
1964:
1142:
17:
2287:"Inferring HIV Transmission Dynamics from Phylogenetic Sequence Relationships"
1886:
418:
2312:
2163:
1924:
763:
113:
2330:
878:
centered on distinct codewords being disjoint. These balls are also called
2401:
2382:
2285:
Pilcher, Christopher D.; Wong, Joseph K.; Pillai, Satish K. (2008-03-18).
2100:
1399:
973:
2756:
2154:
387:
406:
between two sequences. It is named after the American mathematician
1574:
of the result (the number of nonzero bits) using an algorithm of
390:
are different. In other words, it measures the minimum number of
2740:
339:
2449:
766:, and the Hamming distance of the strings is equivalent to the
1398:, computes the Hamming distance between two strings (or other
980: â„ 2 the Hamming distance is applied in case of the
31:
1632:// The ^ operators sets to 1 only the bits that are different
1686:// We then count the bit set to 1 using the Peter Wegner way
652:
is not larger than the sum of the Hamming distances between
717:
binary strings, with the Hamming distance, is known as the
2445:
1048:
both distances coincide because any pair of elements from
937:, who introduced the concept in his fundamental paper on
1118:
differ by 1, but the distances are different for larger
1555:
function merges two equal-length collections in pairs.
996:
because the Lee distance accounts for errors of ±1. If
2424:
Information Theory, Inference, and Learning Algorithms
1492:"Undefined for sequences of unequal length."
1089:
1054:
1739:
A faster alternative is to use the population count (
1124:
1028:
1002:
735:
699:
the Hamming distance is equal to the number of ones (
299:
259:
219:
179:
2383:"A technique for counting ones in a binary computer"
2099:, North-Holland Mathematical Library, vol. 54,
915:-1)/2â errors. The latter number is also called the
2749:
2696:
2663:
2630:
2609:
2551:
2483:
285:
245:
205:
165:
155:
145:
1130:
1110:
1075:
1040:
1014:
750:
596:, then whenever there is a difference between the
314:
274:
234:
194:
870:+1. This is also understood geometrically as any
2095:; Honkala, I.; Litsyn, S.; Lobstein, A. (1997),
2020:
2018:
2016:
2014:
793:) is used to define some essential notions in
725:. One can also view a binary string of length
612:, then there must be a difference between the
27:Number of bits that differ between two strings
2461:
8:
2125:"Error detecting and error correcting codes"
1249:"Strings must be of equal length."
94:
2468:
2454:
2446:
992:or more generally channels susceptible to
943:Error detecting and error correcting codes
903:Thus a code with minimum Hamming distance
799:error detecting and error correcting codes
2400:
2320:
2302:
2201:
2194:Applied Cryptography and Network Security
2153:
2143:
1123:
1104:
1103:
1095:
1091:
1090:
1088:
1069:
1068:
1060:
1056:
1055:
1053:
1027:
1001:
907:between its codewords can detect at most
850:) such that the Hamming distance between
742:
738:
737:
734:
668:. The Hamming distance between two words
298:
258:
218:
178:
82:Learn how and when to remove this message
2640:Comparison of regular-expression engines
421:, in which the equal-length strings are
45:This article includes a list of general
1976:
1811:// Hamming distance for 64-bit integers
1748:// Hamming distance for 32-bit integers
1716:// Set to zero val's lowest-order 1
1111:{\textstyle \mathbb {Z} /3\mathbb {Z} }
1076:{\textstyle \mathbb {Z} /2\mathbb {Z} }
584:as well: Indeed, if we fix three words
2087:
2085:
1722:// Return the number of differing bits
1575:
1570:of the two inputs, and then finds the
93:
2601:ZhuâTakaoka string matching algorithm
1141:The Hamming distance is also used in
644:. Hence the Hamming distance between
7:
2229:Integrated Circuit and System Design
933:The Hamming distance is named after
842:, there exists at most one codeword
774:Error detection and error correction
2566:BoyerâMoore string-search algorithm
2027:An Introduction to Abstract Algebra
2145:10.1002/j.1538-7305.1950.tb00463.x
1145:as a measure of genetic distance.
51:it lacks sufficient corresponding
25:
2655:Nondeterministic finite automaton
2596:Two-way string-matching algorithm
2132:The Bell System Technical Journal
2353: This article incorporates
2348:
2181:from the original on 2022-10-09.
1987:Pulse Code Modulation Techniques
1889:
838:in the underlying Hamming space
751:{\displaystyle \mathbb {R} ^{n}}
347:
331:
121:
105:
36:
2366:General Services Administration
2571:BoyerâMooreâHorspool algorithm
2561:ApostolicoâGiancarlo algorithm
2054:Warren Jr., Henry S. (2013) .
2025:Robinson, Derek J. S. (2003).
309:
303:
269:
263:
229:
223:
189:
183:
1:
2258:Introduction to Coding Theory
2123:Hamming, R. W. (April 1950).
1323:Or, in a shorter expression:
713:. The metric space of length-
116:for finding Hamming distance.
2576:KnuthâMorrisâPratt algorithm
2503:DamerauâLevenshtein distance
2304:10.1371/journal.pmed.0050069
1910:DamerauâLevenshtein distance
911:-1 errors and can correct â(
862:. In other words, a code is
564:, the Hamming distance is a
342:for finding Hamming distance
2767:Compressed pattern matching
2493:Approximate string matching
2203:10.1007/978-3-642-01957-9_7
923:error-correcting capability
2849:
2772:Longest common subsequence
2683:NeedlemanâWunsch algorithm
2553:String-searching algorithm
2429:Cambridge University Press
2262:Cambridge University Press
413:A major application is in
2782:Sequential pattern mining
2622:Commentz-Walter algorithm
2610:Multiple string searching
2543:WagnerâFischer algorithm
2388:Communications of the ACM
1990:. Springer. p. 206.
1960:Sparse distributed memory
1955:SĂžrensen similarity index
99:
2792:String rewriting systems
2777:Longest common substring
2688:SmithâWaterman algorithm
2513:Gestalt pattern matching
1745:
1584:
1405:
1325:
1162:
929:History and applications
780:minimum Hamming distance
676:can also be seen as the
2726:Generalized suffix tree
2650:Thompson's construction
2066:Pearson Education, Inc.
1984:Waggener, Bill (1995).
982:q-ary symmetric channel
417:, more specifically to
354:Two example distances:
128:Two example distances:
66:more precise citations.
2678:Hirschberg's algorithm
2361:Federal Standard 1037C
2355:public domain material
1132:
1112:
1077:
1042:
1016:
994:synchronization errors
770:between the vertices.
752:
316:
276:
236:
196:
2533:Levenshtein automaton
2523:JaroâWinkler distance
2402:10.1145/367236.367286
1935:JaroâWinkler distance
1152:is more appropriate.
1133:
1113:
1078:
1043:
1017:
972:-ary strings over an
753:
317:
277:
237:
197:
2581:RabinâKarp algorithm
2538:Levenshtein distance
2227:Ayala, Jose (2012).
2033:. pp. 255â257.
1945:Mahalanobis distance
1940:Levenshtein distance
1859:__builtin_popcountll
1150:Levenshtein distance
1122:
1087:
1052:
1026:
1000:
786:(usually denoted by
733:
315:{\displaystyle O(n)}
297:
275:{\displaystyle O(n)}
257:
235:{\displaystyle O(1)}
217:
195:{\displaystyle O(n)}
177:
2736:Ternary search tree
2419:MacKay, David J. C.
1920:Gap-Hamming problem
1041:{\displaystyle q=3}
1015:{\displaystyle q=2}
834:if, for every word
801:. In particular, a
691:For binary strings
582:triangle inequality
560:For a fixed length
96:
2665:Sequence alignment
2632:Regular expression
2256:Roth, Ron (2006).
2103:, pp. 16â17,
1915:Euclidean distance
1897:Mathematics portal
1817:hamming_distance64
1790:__builtin_popcount
1754:hamming_distance32
1580:__builtin_popcount
1392:hamming_distance()
1128:
1108:
1073:
1038:
1012:
990:phase-shift keying
947:information theory
890:1-error correcting
832:k-error correcting
768:Manhattan distance
748:
568:on the set of the
402:for measuring the
376:information theory
312:
272:
232:
192:
2805:
2804:
2797:String operations
2271:978-0-521-84504-5
2242:978-3-642-36156-2
2213:978-3-642-01957-9
2110:978-0-08-053007-9
2075:978-0-321-84268-8
2040:978-3-11-019816-4
2031:Walter de Gruyter
1997:978-0-442-01436-0
1950:Mannheim distance
1394:, implemented in
1156:Algorithm example
1131:{\displaystyle q}
962:telecommunication
884:in this context.
628:, or between the
576:(also known as a
325:
324:
150:String similarity
141:
140:
92:
91:
84:
16:(Redirected from
2840:
2762:Pattern matching
2716:Suffix automaton
2518:Hamming distance
2470:
2463:
2456:
2447:
2442:
2414:
2404:
2374:
2373:
2368:. Archived from
2352:
2351:
2335:
2334:
2324:
2306:
2282:
2276:
2275:
2253:
2247:
2246:
2224:
2218:
2217:
2205:
2189:
2183:
2182:
2180:
2157:
2147:
2129:
2120:
2114:
2113:
2089:
2080:
2079:
2078:. 0-321-84268-5.
2068:pp. 81â96.
2057:Hacker's Delight
2051:
2045:
2044:
2022:
2009:
2008:
2006:
2004:
1981:
1899:
1894:
1893:
1878:
1875:
1872:
1869:
1866:
1863:
1860:
1857:
1854:
1851:
1848:
1845:
1842:
1839:
1836:
1833:
1830:
1827:
1824:
1821:
1818:
1815:
1812:
1809:
1806:
1803:
1800:
1797:
1794:
1791:
1788:
1785:
1782:
1779:
1776:
1773:
1770:
1767:
1764:
1761:
1758:
1755:
1752:
1749:
1735:
1732:
1729:
1726:
1723:
1720:
1717:
1714:
1711:
1708:
1705:
1702:
1699:
1696:
1693:
1690:
1687:
1684:
1681:
1678:
1675:
1672:
1669:
1666:
1663:
1660:
1657:
1654:
1651:
1648:
1645:
1642:
1639:
1636:
1633:
1630:
1627:
1624:
1621:
1618:
1615:
1612:
1609:
1606:
1603:
1600:
1597:
1594:
1591:
1590:hamming_distance
1588:
1547:
1544:
1541:
1538:
1535:
1532:
1529:
1526:
1523:
1520:
1517:
1514:
1511:
1508:
1505:
1502:
1499:
1496:
1493:
1490:
1487:
1484:
1481:
1478:
1475:
1472:
1469:
1466:
1463:
1460:
1457:
1454:
1451:
1448:
1445:
1442:
1439:
1436:
1433:
1430:
1427:
1424:
1421:
1418:
1415:
1412:
1411:hamming_distance
1409:
1393:
1386:
1383:
1380:
1377:
1374:
1371:
1368:
1365:
1362:
1359:
1356:
1353:
1350:
1347:
1344:
1341:
1338:
1335:
1332:
1329:
1319:
1316:
1313:
1310:
1307:
1304:
1301:
1298:
1295:
1292:
1289:
1286:
1283:
1280:
1277:
1274:
1271:
1268:
1265:
1262:
1259:
1256:
1253:
1250:
1247:
1244:
1241:
1238:
1235:
1232:
1229:
1226:
1223:
1220:
1217:
1214:
1211:
1208:
1205:
1202:
1199:
1196:
1193:
1190:
1187:
1184:
1181:
1178:
1175:
1172:
1169:
1168:hamming_distance
1166:
1137:
1135:
1134:
1129:
1117:
1115:
1114:
1109:
1107:
1099:
1094:
1082:
1080:
1079:
1074:
1072:
1064:
1059:
1047:
1045:
1044:
1039:
1021:
1019:
1018:
1013:
784:minimum distance
757:
755:
754:
749:
747:
746:
741:
701:population count
548:
544:
536:
532:
523:
517:
508:
500:
489:
485:
477:
473:
462:
454:
380:Hamming distance
361:
358:has distance 3;
357:
351:
335:
321:
319:
318:
313:
290:space complexity
281:
279:
278:
273:
241:
239:
238:
233:
201:
199:
198:
193:
135:
132:has distance 3;
131:
125:
109:
101:
100:
97:
95:Hamming distance
87:
80:
76:
73:
67:
62:this article by
53:inline citations
40:
39:
32:
21:
18:Hamming Distance
2848:
2847:
2843:
2842:
2841:
2839:
2838:
2837:
2828:Metric geometry
2808:
2807:
2806:
2801:
2745:
2692:
2659:
2645:Regular grammar
2626:
2605:
2586:Raita algorithm
2547:
2498:Bitap algorithm
2479:
2474:
2439:
2417:
2377:
2358:
2349:
2347:
2344:
2342:Further reading
2339:
2338:
2284:
2283:
2279:
2272:
2264:. p. 298.
2255:
2254:
2250:
2243:
2226:
2225:
2221:
2214:
2191:
2190:
2186:
2178:
2127:
2122:
2121:
2117:
2111:
2091:
2090:
2083:
2076:
2053:
2052:
2048:
2041:
2024:
2023:
2012:
2002:
2000:
1998:
1983:
1982:
1978:
1973:
1895:
1888:
1885:
1880:
1879:
1876:
1873:
1870:
1867:
1864:
1861:
1858:
1855:
1852:
1849:
1846:
1843:
1840:
1837:
1834:
1831:
1828:
1825:
1822:
1819:
1816:
1813:
1810:
1807:
1804:
1801:
1798:
1795:
1792:
1789:
1786:
1783:
1780:
1777:
1774:
1771:
1768:
1765:
1762:
1759:
1756:
1753:
1750:
1747:
1737:
1736:
1733:
1730:
1727:
1724:
1721:
1718:
1715:
1712:
1709:
1706:
1703:
1700:
1697:
1694:
1691:
1688:
1685:
1682:
1679:
1676:
1673:
1670:
1667:
1664:
1661:
1658:
1655:
1652:
1649:
1646:
1643:
1640:
1637:
1634:
1631:
1628:
1625:
1622:
1619:
1616:
1613:
1610:
1607:
1604:
1601:
1598:
1595:
1592:
1589:
1586:
1549:
1548:
1545:
1542:
1539:
1536:
1533:
1530:
1527:
1524:
1521:
1518:
1515:
1512:
1509:
1506:
1503:
1500:
1497:
1494:
1491:
1488:
1485:
1482:
1479:
1476:
1473:
1470:
1467:
1464:
1461:
1458:
1455:
1452:
1449:
1446:
1443:
1440:
1437:
1434:
1431:
1428:
1425:
1422:
1419:
1416:
1413:
1410:
1407:
1391:
1388:
1387:
1384:
1381:
1378:
1375:
1372:
1369:
1366:
1363:
1360:
1357:
1354:
1351:
1348:
1345:
1342:
1339:
1336:
1333:
1330:
1327:
1321:
1320:
1317:
1314:
1311:
1308:
1305:
1302:
1299:
1296:
1293:
1290:
1287:
1284:
1281:
1278:
1275:
1272:
1269:
1266:
1263:
1260:
1257:
1254:
1251:
1248:
1245:
1242:
1239:
1236:
1233:
1230:
1227:
1224:
1221:
1218:
1215:
1212:
1209:
1206:
1203:
1200:
1197:
1194:
1191:
1188:
1185:
1182:
1179:
1176:
1173:
1170:
1167:
1164:
1158:
1120:
1119:
1085:
1084:
1050:
1049:
1024:
1023:
998:
997:
966:signal distance
935:Richard Hamming
931:
881:Hamming spheres
791:
776:
736:
731:
730:
729:as a vector in
723:hypercube graph
558:
546:
542:
534:
530:
521:
515:
506:
498:
487:
483:
475:
471:
460:
452:
443:
435:
408:Richard Hamming
372:
371:
370:
369:
365:
364:
363:
359:
355:
352:
344:
343:
336:
295:
294:
255:
254:
215:
214:
175:
174:
137:
133:
129:
126:
117:
110:
88:
77:
71:
68:
58:Please help to
57:
41:
37:
28:
23:
22:
15:
12:
11:
5:
2846:
2844:
2836:
2835:
2830:
2825:
2820:
2818:String metrics
2810:
2809:
2803:
2802:
2800:
2799:
2794:
2789:
2784:
2779:
2774:
2769:
2764:
2759:
2753:
2751:
2747:
2746:
2744:
2743:
2738:
2733:
2728:
2723:
2718:
2713:
2708:
2702:
2700:
2698:Data structure
2694:
2693:
2691:
2690:
2685:
2680:
2675:
2669:
2667:
2661:
2660:
2658:
2657:
2652:
2647:
2642:
2636:
2634:
2628:
2627:
2625:
2624:
2619:
2613:
2611:
2607:
2606:
2604:
2603:
2598:
2593:
2591:Trigram search
2588:
2583:
2578:
2573:
2568:
2563:
2557:
2555:
2549:
2548:
2546:
2545:
2540:
2535:
2530:
2525:
2520:
2515:
2510:
2505:
2500:
2495:
2489:
2487:
2481:
2480:
2475:
2473:
2472:
2465:
2458:
2450:
2444:
2443:
2437:
2415:
2375:
2372:on 2022-01-22.
2343:
2340:
2337:
2336:
2277:
2270:
2248:
2241:
2235:. p. 62.
2219:
2212:
2184:
2138:(2): 147â160.
2115:
2109:
2097:Covering Codes
2081:
2074:
2062:Addison Wesley
2060:(2 ed.).
2046:
2039:
2010:
1996:
1975:
1974:
1972:
1969:
1968:
1967:
1962:
1957:
1952:
1947:
1942:
1937:
1932:
1927:
1922:
1917:
1912:
1907:
1905:Closest string
1901:
1900:
1884:
1881:
1746:
1585:
1572:Hamming weight
1558:The following
1406:
1326:
1163:
1157:
1154:
1127:
1106:
1102:
1098:
1093:
1071:
1067:
1063:
1058:
1037:
1034:
1031:
1011:
1008:
1005:
960:It is used in
930:
927:
918:packing radius
830:is said to be
808:is said to be
789:
775:
772:
745:
740:
678:Hamming weight
557:
554:
553:
552:
526:
512:
493:
466:
442:
439:
434:
431:
400:string metrics
367:
366:
362:has distance 2
353:
346:
345:
337:
330:
329:
328:
327:
326:
323:
322:
311:
308:
305:
302:
292:
283:
282:
271:
268:
265:
262:
252:
243:
242:
231:
228:
225:
222:
212:
203:
202:
191:
188:
185:
182:
172:
163:
162:
157:
156:Data structure
153:
152:
147:
143:
142:
139:
138:
136:has distance 1
127:
120:
118:
111:
104:
90:
89:
44:
42:
35:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
2845:
2834:
2831:
2829:
2826:
2824:
2823:Coding theory
2821:
2819:
2816:
2815:
2813:
2798:
2795:
2793:
2790:
2788:
2785:
2783:
2780:
2778:
2775:
2773:
2770:
2768:
2765:
2763:
2760:
2758:
2755:
2754:
2752:
2748:
2742:
2739:
2737:
2734:
2732:
2729:
2727:
2724:
2722:
2719:
2717:
2714:
2712:
2709:
2707:
2704:
2703:
2701:
2699:
2695:
2689:
2686:
2684:
2681:
2679:
2676:
2674:
2671:
2670:
2668:
2666:
2662:
2656:
2653:
2651:
2648:
2646:
2643:
2641:
2638:
2637:
2635:
2633:
2629:
2623:
2620:
2618:
2615:
2614:
2612:
2608:
2602:
2599:
2597:
2594:
2592:
2589:
2587:
2584:
2582:
2579:
2577:
2574:
2572:
2569:
2567:
2564:
2562:
2559:
2558:
2556:
2554:
2550:
2544:
2541:
2539:
2536:
2534:
2531:
2529:
2526:
2524:
2521:
2519:
2516:
2514:
2511:
2509:
2508:Edit distance
2506:
2504:
2501:
2499:
2496:
2494:
2491:
2490:
2488:
2486:
2485:String metric
2482:
2478:
2471:
2466:
2464:
2459:
2457:
2452:
2451:
2448:
2440:
2438:0-521-64298-1
2434:
2430:
2427:. Cambridge:
2426:
2425:
2420:
2416:
2412:
2408:
2403:
2398:
2394:
2390:
2389:
2384:
2380:
2379:Wegner, Peter
2376:
2371:
2367:
2363:
2362:
2356:
2346:
2345:
2341:
2332:
2328:
2323:
2318:
2314:
2310:
2305:
2300:
2296:
2292:
2291:PLOS Medicine
2288:
2281:
2278:
2273:
2267:
2263:
2259:
2252:
2249:
2244:
2238:
2234:
2230:
2223:
2220:
2215:
2209:
2204:
2199:
2195:
2188:
2185:
2177:
2173:
2169:
2165:
2161:
2156:
2151:
2146:
2141:
2137:
2133:
2126:
2119:
2116:
2112:
2106:
2102:
2098:
2094:
2088:
2086:
2082:
2077:
2071:
2067:
2063:
2059:
2058:
2050:
2047:
2042:
2036:
2032:
2028:
2021:
2019:
2017:
2015:
2011:
1999:
1993:
1989:
1988:
1980:
1977:
1970:
1966:
1963:
1961:
1958:
1956:
1953:
1951:
1948:
1946:
1943:
1941:
1938:
1936:
1933:
1931:
1930:Jaccard index
1928:
1926:
1923:
1921:
1918:
1916:
1913:
1911:
1908:
1906:
1903:
1902:
1898:
1892:
1887:
1882:
1744:
1742:
1583:
1581:
1577:
1576:Wegner (1960)
1573:
1569:
1566:
1561:
1556:
1554:
1404:
1401:
1397:
1390:The function
1324:
1161:
1155:
1153:
1151:
1146:
1144:
1139:
1125:
1100:
1096:
1065:
1061:
1035:
1032:
1029:
1009:
1006:
1003:
995:
991:
987:
983:
979:
975:
971:
967:
963:
958:
956:
952:
951:coding theory
948:
944:
940:
939:Hamming codes
936:
928:
926:
925:of the code.
924:
920:
919:
914:
910:
906:
901:
899:
895:
891:
885:
883:
882:
877:
873:
869:
865:
861:
857:
853:
849:
845:
841:
837:
833:
829:
824:
822:
817:
815:
811:
807:
804:
800:
796:
795:coding theory
792:
785:
781:
773:
771:
769:
765:
762:-dimensional
761:
743:
728:
724:
720:
716:
712:
709:
706:
702:
698:
694:
689:
687:
683:
679:
675:
671:
667:
663:
659:
655:
651:
647:
643:
640:th letter of
639:
635:
632:th letter of
631:
627:
624:th letter of
623:
619:
616:th letter of
615:
611:
608:th letter of
607:
603:
600:th letter of
599:
595:
591:
587:
583:
579:
578:Hamming space
575:
571:
567:
563:
555:
550:
538:
527:
524:
518:
513:
510:
502:
494:
491:
479:
467:
464:
456:
448:
447:
446:
440:
438:
432:
430:
428:
424:
420:
416:
415:coding theory
411:
409:
405:
404:edit distance
401:
397:
393:
392:substitutions
389:
385:
381:
377:
350:
341:
338:3-bit binary
334:
306:
300:
293:
291:
288:
284:
266:
260:
253:
251:
248:
244:
226:
220:
213:
211:
208:
204:
186:
180:
173:
171:
168:
164:
161:
158:
154:
151:
148:
144:
124:
119:
115:
112:4-bit binary
108:
103:
102:
98:
86:
83:
75:
65:
61:
55:
54:
48:
43:
34:
33:
30:
19:
2711:Suffix array
2617:AhoâCorasick
2528:Lee distance
2517:
2423:
2392:
2386:
2370:the original
2360:
2294:
2290:
2280:
2257:
2251:
2228:
2222:
2193:
2187:
2135:
2131:
2118:
2096:
2056:
2049:
2026:
2001:. Retrieved
1986:
1979:
1740:
1738:
1568:exclusive or
1557:
1550:
1389:
1322:
1318:dist_counter
1306:dist_counter
1255:dist_counter
1159:
1147:
1140:
988:is used for
986:Lee distance
984:, while the
977:
969:
965:
959:
955:cryptography
942:
932:
922:
916:
912:
908:
904:
902:
897:
893:
889:
886:
879:
875:
872:closed balls
867:
863:
859:
855:
851:
847:
843:
839:
835:
831:
827:
825:
820:
818:
813:
809:
805:
787:
783:
779:
777:
759:
726:
719:Hamming cube
718:
714:
710:
704:
696:
692:
690:
685:
681:
673:
669:
665:
661:
660:and between
657:
653:
649:
645:
641:
637:
633:
629:
625:
621:
617:
613:
609:
605:
601:
597:
593:
589:
585:
573:
561:
559:
540:
528:
520:
514:
504:
496:
481:
469:
458:
450:
444:
436:
427:finite field
412:
395:
391:
382:between two
379:
373:
78:
69:
50:
29:
2721:Suffix tree
2155:10945/46756
1965:Word ladder
1143:systematics
858:is at most
419:block codes
250:performance
210:performance
170:performance
64:introducing
2812:Categories
2395:(5): 322.
2297:(3): e69.
1971:References
1551:where the
1486:ValueError
1243:ValueError
892:, that is
874:of radius
797:, such as
572:of length
556:Properties
433:Definition
287:Worst-case
167:Worst-case
47:references
2313:1549-1676
2164:0005-8580
2093:Cohen, G.
1925:Gray code
764:hypercube
503:" and "
480:" and "
457:" and "
207:Best-case
134:0110â1110
130:0100â1001
114:tesseract
2421:(2003).
2411:31683715
2381:(1960).
2331:18351799
2233:Springer
2176:Archived
2172:61141773
2101:Elsevier
1883:See also
1838:unsigned
1823:unsigned
1772:unsigned
1760:unsigned
1741:popcount
1641:unsigned
1605:unsigned
1596:unsigned
1400:iterable
1396:Python 3
976:of size
974:alphabet
898:2k+1 = 3
636:and the
604:and the
511:" is 4.
492:" is 3.
465:" is 3.
441:Examples
72:May 2015
2787:Sorting
2757:Parsing
2477:Strings
2322:2267810
2003:13 June
1565:bitwise
1370:string2
1364:string1
1300:string2
1294:string1
1285:string1
1234:string2
1219:string1
1186:string2
1174:string1
921:or the
826:A code
425:over a
423:vectors
388:symbols
384:strings
360:010â111
356:100â011
247:Average
60:improve
2435:
2409:
2329:
2319:
2311:
2268:
2239:
2210:
2170:
2162:
2107:
2072:
2037:
1994:
1856:return
1787:return
1725:return
1498:return
1376:strict
1315:return
968:. For
953:, and
846:(from
566:metric
396:errors
378:, the
160:string
49:, but
2833:Cubes
2750:Other
2706:DAFSA
2673:BLAST
2407:S2CID
2357:from
2179:(PDF)
2168:S2CID
2128:(PDF)
1698:&
1553:zip()
1525:char2
1519:char1
1513:char2
1507:char1
1483:raise
1441:->
1352:char2
1346:char1
1340:char2
1334:char1
1273:range
1240:raise
1198:->
703:) in
570:words
551:is 3.
539:and
525:is 4.
519:and
146:Class
2741:Trie
2731:Rope
2433:ISBN
2327:PMID
2309:ISSN
2266:ISBN
2237:ISBN
2208:ISBN
2160:ISSN
2105:ISBN
2070:ISBN
2035:ISBN
2005:2020
1992:ISBN
1844:long
1841:long
1829:long
1826:long
1728:dist
1677:dist
1665:>
1620:dist
1382:True
854:and
816:+1.
803:code
778:The
695:and
672:and
664:and
656:and
648:and
620:and
592:and
522:1111
516:0000
507:erst
499:athr
340:cube
2397:doi
2317:PMC
2299:doi
2198:doi
2150:hdl
2140:doi
1814:int
1775:int
1763:int
1751:int
1704:val
1695:val
1689:val
1662:val
1644:val
1635:for
1617:int
1587:int
1531:zip
1516:for
1501:sum
1471:len
1456:len
1444:int
1435:str
1423:str
1408:def
1358:zip
1343:for
1328:sum
1288:)):
1279:len
1264:for
1228:len
1213:len
1201:int
1192:str
1180:str
1165:def
1083:or
1022:or
894:k=1
790:min
782:or
708:XOR
680:of
461:thr
453:rol
374:In
2814::
2431:.
2405:.
2391:.
2385:.
2364:.
2325:.
2315:.
2307:.
2293:.
2289:.
2260:.
2231:.
2206:.
2174:.
2166:.
2158:.
2148:.
2136:29
2134:.
2130:.
2084:^
2064:â
2029:.
2013:^
1874:);
1805:);
1713:);
1674:++
1546:))
1543:s2
1537:s1
1528:in
1510:!=
1480:):
1477:s2
1468:!=
1462:s1
1453:if
1429:s2
1417:s1
1385:))
1355:in
1337:!=
1309:+=
1297:!=
1291:if
1270:in
1237:):
1225:!=
1210:if
1138:.
957:.
949:,
941:,
900:.
684:â
588:,
549:96
543:23
537:96
531:17
509:in
501:in
490:in
488:st
478:in
476:ol
463:in
459:ka
455:in
451:ka
429:.
410:.
2469:e
2462:t
2455:v
2441:.
2413:.
2399::
2393:3
2333:.
2301::
2295:5
2274:.
2245:.
2216:.
2200::
2152::
2142::
2043:.
2007:.
1877:}
1871:y
1868:^
1865:x
1862:(
1853:{
1850:)
1847:y
1835:,
1832:x
1820:(
1808:}
1802:y
1799:^
1796:x
1793:(
1784:{
1781:)
1778:y
1769:,
1766:x
1757:(
1734:}
1731:;
1719:}
1710:1
1707:-
1701:(
1692:=
1683:{
1680:)
1671:;
1668:0
1659:;
1656:y
1653:^
1650:x
1647:=
1638:(
1629:;
1626:0
1623:=
1614:{
1611:)
1608:y
1602:,
1599:x
1593:(
1560:C
1540:,
1534:(
1522:,
1504:(
1495:)
1489:(
1474:(
1465:)
1459:(
1447::
1438:)
1432::
1426:,
1420::
1414:(
1379:=
1373:,
1367:,
1361:(
1349:,
1331:(
1312:1
1303::
1282:(
1276:(
1267:n
1261:0
1258:=
1252:)
1246:(
1231:(
1222:)
1216:(
1204::
1195:)
1189::
1183:,
1177::
1171:(
1126:q
1105:Z
1101:3
1097:/
1092:Z
1070:Z
1066:2
1062:/
1057:Z
1036:3
1033:=
1030:q
1010:2
1007:=
1004:q
978:q
970:q
913:d
909:d
905:d
876:k
868:k
864:k
860:k
856:c
852:w
848:C
844:c
840:H
836:w
828:C
821:k
814:k
810:k
806:C
788:d
760:n
744:n
739:R
727:n
715:n
711:b
705:a
697:b
693:a
686:b
682:a
674:b
670:a
666:c
662:b
658:b
654:a
650:c
646:a
642:c
638:i
634:b
630:i
626:b
622:i
618:a
614:i
610:c
606:i
602:a
598:i
594:c
590:b
586:a
574:n
562:n
547:7
545:3
541:2
535:8
533:3
529:2
505:k
497:k
495:"
486:r
484:e
482:k
474:r
472:a
470:k
468:"
449:"
310:)
307:n
304:(
301:O
270:)
267:n
264:(
261:O
230:)
227:1
224:(
221:O
190:)
187:n
184:(
181:O
85:)
79:(
74:)
70:(
56:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
