science

String metric

String metric is a science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand String metric rather than just read about it. In short: In mathematics and computer science, a string metric (also known as a string similarity metric or string distance function) is a metric that measures distance ("inverse similarity") between two text strings for approximate string matching or comparison and in fuzzy string searching. A requirement for a string metric (e.g. in contrast to string matching) is fulfillment of the triangle inequality.

Key takeaways

String metric belongs to science; place it in that map before memorising details.
Learn the definition first, then one example that makes the definition concrete.
Connect String metric to a quantity you can measure, compute or draw — that is where exam questions come from.
Reproduce the core statement of String metric from memory before moving on to harder problems.

Reference excerpt

In mathematics and computer science, a string metric (also known as a string similarity metric or string distance function) is a metric that measures distance ("inverse similarity") between two text strings for approximate string matching or comparison and in fuzzy string searching. A requirement for a string metric (e.g. in contrast to string matching) is fulfillment of the triangle inequality. For example, the strings "Sam" and "Samuel" can be considered to be close. A string metric provides a number indicating an algorithm-specific indication of distance. The most widely known string metric is a rudimentary one called the Levenshtein distance (also known as edit distance). It operates between two input strings, returning a number equivalent to the number of substitutions and deletions needed in order to transform one input string into another. Simplistic string metrics such as Levenshtein distance have expanded to include phonetic, token, grammatical and character-based methods of statistical comparisons. String metrics are used heavily in information integration and are currently used in areas including fraud detection, fingerprint analysis, plagiarism detection, ontology merging, DNA analysis, RNA analysis, image analysis, evidence-based machine learning, database data deduplication, data mining, incremental search, data integration, malware detection, and semantic knowledge integration.

List of string metrics Levenshtein distance, or its generalization edit distance Damerau–Levenshtein distance Sørensen–Dice coefficient Block distance or L1 distance or City block distance Hamming distance Simple matching coefficient (SMC) Jaccard similarity or Jaccard coefficient or Tanimoto coefficient Tversky index Overlap coefficient Variational distance Hellinger distance or Bhattacharyya distance Information radius (Jensen–Shannon divergence) Skew divergence Confusion probability Tau metric, an approximation of the Kullback–Leibler divergence Fellegi and Sunters metric (SFS) Maximal matches Grammar-based distance TFIDF distance metric There also exist functions which measure a dissimilarity between strings, but do not necessarily fulfill the triangle inequality, and as such are not metrics in the mathematical sense. An example of such function is the Jaro–Winkler distance.

Selected string measures examples

References

External links String Similarity Metrics for Information Integration A fairly complete overview Archive index at the Wayback Machine Carnegie Mellon University open source library StringMetric project a Scala library of string metrics and phonetic algorithms Natural project a JavaScript natural language processing library which includes implementations of popular string metrics

Worked examples

Example 1 — a first encounter with String metric

Start with the simplest possible case. Write down what String metric claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to String metric before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about String metric ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of String metric

In research: String metric appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry: Engineering practice reuses String metric in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom: String metric is common in secondary-school and first-year university syllabi. It links to neighbouring topics Metrics, String metrics, so understanding it makes those chapters shorter.
In everyday life: Look for String metric outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study String metric in 20 minutes

Read the reference excerpt below once, without taking notes.
Close the page and write down what String metric means in your own words.
Compare your version with the excerpt and mark what you missed.
Work through the three examples above with pen and paper.
Explain String metric out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is String metric in simple terms?

Why does String metric matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study String metric?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on String metric.