Yvonne81’s Weblog

From Wikipedia, the free encyclopedia

Schrödinger’s cat is a seemingly paradoxical thought experiment devised by Erwin Schrödinger that attempts to illustrate the incompleteness of the Copenhagen interpretation when going from subatomic to macroscopic systems. Schrödinger proposed his “cat”, after a suggestion of Albert Einstein’s, stating that if a scenario existed where a cat could be so isolated from external interference (decoherence), the state of the cat can only be known as a superposition (combination) of possible rest states (eigenstates), because finding out (measuring the state) cannot be done without the observer interfering with the experiment — the measurement system (the observer) is entangled with the experiment.

The thought experiment serves to illustrate the strangeness of quantum mechanics and the mathematics necessary to describe quantum states. The idea of a particle existing in a superposition of possible states, while a fact of quantum mechanics, is a concept that does not easily scale to large systems (like cats), which are not indeterminably probabilistic in nature. Philosophically, these positions which emphasize either probability or determined outcomes are called (respectively) positivism and determinism.

//

[edit] The thought experiment

Schrödinger wrote:

One can even set up quite ridiculous cases. A cat is penned up in a steel chamber, along with the following device (which must be secured against direct interference by the cat): in a Geiger counter there is a tiny bit of radioactive substance, so small, that perhaps in the course of the hour one of the atoms decays, but also, with equal probability, perhaps none; if it happens, the counter tube discharges and through a relay releases a hammer which shatters a small flask of hydrocyanic acid. If one has left this entire system to itself for an hour, one would say that the cat still lives if meanwhile no atom has decayed. The psi-function of the entire system would express this by having in it the living and dead cat (pardon the expression) mixed or smeared out in equal parts.

It is typical of these cases that an indeterminacy originally restricted to the atomic domain becomes transformed into macroscopic indeterminacy, which can then be resolved by direct observation. That prevents us from so naively accepting as valid a “blurred model” for representing reality. In itself it would not embody anything unclear or contradictory. There is a difference between a shaky or out-of-focus photograph and a snapshot of clouds and fog banks.^[1]

The experiment must be shielded from the environment to prevent quantum decoherence from inducing wavefunction collapse.

An illustration of both states, a dead and living cat. According to quantum theory, after an hour the cat is in a quantum superposition of coexisting alive and dead states. Yet when we look in the box we expect to see only one of the states, not a mixture of them.

The above text is a translation of two paragraphs from a much larger original article, which appeared in the German magazine Naturwissenschaften (“Natural Sciences”) in 1935.^[2]

It was intended as a discussion of the EPR article published by Einstein, Podolsky and Rosen in the same year. Apart from introducing the cat, Schrödinger also coined the term “entanglement” (German: Verschränkung) in his article.

Schrödinger’s famous Gedankenexperiment poses the question: when does a quantum system stop existing as a mixture of states and become one or the other? (More technically, when does the actual quantum state stop being a linear combination of states, each of which resemble different classical states, and instead begin to have a unique classical description?) If the cat survives, it remembers only being alive. But explanations of the EPR experiments that are consistent with standard microscopic quantum mechanics require that macroscopic objects, such as cats and notebooks, do not always have unique classical descriptions. The purpose of the thought experiment is to illustrate this apparent paradox: our intuition says that no observer can be in a mixture of states, yet it seems only cats can be such a mixture. Are cats required to be observers, or does their existence in a single well-defined classical state require another external observer? Each alternative seemed absurd to Albert Einstein, who was impressed by the ability of the thought experiment to highlight these issues; in a letter to Schrödinger dated 1950 he wrote:

You are the only contemporary physicist, besides Laue, who sees that one cannot get around the assumption of reality—if only one is honest. Most of them simply do not see what sort of risky game they are playing with reality—reality as something independent of what is experimentally established. Their interpretation is, however, refuted most elegantly by your system of radioactive atom + amplifier + charge of gun powder + cat in a box, in which the psi-function of the system contains both the cat alive and blown to bits. Nobody really doubts that the presence or absence of the cat is something independent of the act of observation.

But perhaps it was inevitable that Einstein would be impressed with Schrödinger’s cat—Einstein had previously suggested to Schrödinger a similar paradox involving an unstable keg of gunpowder, instead of a cat. Schrödinger had taken the next step of applying quantum mechanics to an entity that may or may not be conscious, to further illustrate the putative incompleteness of quantum mechanics.

[edit] Copenhagen interpretation

Quantum physics

This box: view • talk • edit

In the Copenhagen interpretation of quantum mechanics, a system stops being a superposition of states and becomes either one or the other when an observation takes place. This experiment makes apparent the fact that the nature of measurement, or observation, is not well defined in this interpretation. Some interpret the experiment to mean that while the box is closed, the system simultaneously exists in a superposition of the states “decayed nucleus/dead cat” and “undecayed nucleus/living cat”, and that only when the box is opened and an observation performed does the wave function collapse into one of the two states. More intuitively, some feel that the “observation” is taken when a particle from the nucleus hits the detector. This line of thinking can be developed into Objective collapse theories. In contrast, the many worlds approach denies that collapse ever occurs.

Steven Weinberg said:

All this familiar story is true, but it leaves out an irony. Bohr’s version of quantum mechanics was deeply flawed, but not for the reason Einstein thought. The Copenhagen interpretation describes what happens when an observer makes a measurement, but the observer and the act of measurement are themselves treated classically. This is surely wrong: Physicists and their apparatus must be governed by the same quantum mechanical rules that govern everything else in the universe. But these rules are expressed in terms of a wavefunction (or, more precisely, a state vector) that evolves in a perfectly deterministic way. So where do the probabilistic rules of the Copenhagen interpretation come from?

Considerable progress has been made in recent years toward the resolution of the problem, which I cannot go into here. It is enough to say that neither Bohr nor Einstein had focused on the real problem with quantum mechanics. The Copenhagen rules clearly work, so they have to be accepted. But this leaves the task of explaining them by applying the deterministic equation for the evolution of the wavefunction, the Schrödinger equation, to observers and their apparatus.^[3]

Physicist Stephen Hawking once said, “When I hear of Schrödinger’s cat, I reach for my gun,” paraphrasing German playwright and Nazi Poet Laureate Hanns Johst’s famous phrase “Wenn ich ‘Kultur’ höre, entsichere ich meinen Browning!” (“When I hear the word ‘culture’, I release the safety on my Browning,” often paraphrased as something like, “When I hear the word ‘culture,’ I reach for my gun.”)

[edit] Everett many-worlds interpretation & consistent histories

In the many-worlds interpretation of quantum mechanics, which does not single out observation as a special process, both states persist, but are decoherent from each other. In other words, when the box is opened, that part of the universe containing the observer and cat is split into two separate universes, one containing an observer looking at a box with a dead cat, one containing an observer looking at a box with a live cat.

Since the dead and alive states are decoherent, there is no effective communication or interaction between them. When an observer opens the box, they become entangled with the cat, so observer-states corresponding to the cat being alive and dead are formed, and each can have no interaction with the other. The same mechanism of quantum decoherence is also important for the interpretation in terms of Consistent Histories. Only the “dead cat” or “alive cat” can be a part of a consistent history in this interpretation.

Roger Penrose criticises this:

“I wish to make it clear that, as it stands this is far from a resolution of the cat paradox. For there is nothing in the formalism of quantum mechanics that demands that a state of consciousness cannot involve the simultaneous perception of a live and a dead cat”.^[4]

although the mainstream view (without necessarily endorsing many-worlds) is that decoherence is the mechanism that forbids such simultaneous perception.^[5][6]

[edit] Ensemble interpretation

The Ensemble Interpretation states that superpositions are nothing but subensembles of a larger statistical ensemble. That being the case, the state vector would not apply to individual cat experiments, but only to the statistics of many similar prepared cat experiments. Proponents of this interpretation state that this makes the Schrödinger’s cat paradox a trivial non issue.

Taking this interpretation, one forever discards the idea that a single physical system has a mathematical description which corresponds to it in any way.

[edit] Objective collapse theories

According to objective collapse theories, superpositions are destroyed spontaneously (irrespective of external observation) when some objective physical threshold (of time, mass, temperature, irreversibility etc) is reached. Thus, the cat would be expected to have settled into a definite state long before the box is opened. This could loosely be phrased as “the cat observes itself”, or “the environment observes the cat”.

Objective collapse theories require a modification of standard quantum mechanics, to allow superpositions to be destroyed by the process of time-evolution.

[edit] Practical applications

The experiment is a purely theoretical one, and the machine proposed is not known to have been constructed. Analogous effects, however, have some practical use in quantum computing and quantum cryptography. It is possible to send light that is in a superposition of states down a fiber optic cable. Placing a wiretap in the middle of the cable which intercepts and retransmits the transmission will collapse the wavefunction (in the Copenhagen interpretation, “perform an observation”) and cause the light to fall into one state or another. By performing statistical tests on the light received at the other end of the cable, one can tell whether it remains in the superposition of states or has already been observed and retransmitted. In principle, this allows the development of communication systems that cannot be tapped without the tap being noticed at the other end. This experiment can be argued to illustrate that “observation” in the Copenhagen interpretation has nothing to do with consciousness (unless some version of Panpsychism is true), in that a perfectly unconscious wiretap will cause the statistics at the end of the wire to be different . Yet, one still cannot factor out the observation of the wiretap as having an effect upon the outcome.^{[citation needed]}

In quantum computing, the phrase “cat state” often refers to the special entanglement of qubits where the qubits are in an equal superposition of all being 0 and all being 1, i.e. + .

[edit] Extensions

Although discussion of this thought experiment talks about two possible states, in reality there would be a huge number of possible states, since the temperature and degree and state of decomposition of the cat would depend on exactly when and how, as well as if, the mechanism was triggered, as well as the state of the cat prior to death.

A variant of the Schrödinger’s Cat experiment known as the quantum suicide machine has been proposed by cosmologist Max Tegmark. It examines the Schrödinger’s Cat experiment from the point of view of the cat, and argues that this may be able to distinguish between the Copenhagen interpretation and many worlds. Another variant on the experiment is Wigner’s friend.

[edit] See also

• Basis function
• Double-slit experiment
• Interpretations of quantum mechanics
• Quantum Zeno effect
• Elitzur-Vaidman bomb-tester
• Wigner’s friend
• Quantum suicide
• Schrödinger’s cat in popular culture
• Schroedinbug

[edit] References

1. ^ http://www.tu-harburg.de/rzt/rzt/it/QM/cat.html#sect5
2. ^ Schrödinger, Erwin (November 1935). “Die gegenwärtige Situation in der Quantenmechanik (The present situation in quantum mechanics)”. Naturwissenschaften.
3. ^ Weinberg, Steven (November 2005). “Einstein’s Mistakes”. Physics Today: 31.
4. ^ Penrose, R. The Road to Reality, p807.
5. ^ Wojciech H. Zurek, Decoherence, einselection, and the quantum origins of the classical, Reviews of Modern Physics 2003, 75, 715 or [1]
6. ^ Wojciech H. Zurek, Decoherence and the transition from quantum to classical, Physics Today, 44, pp 36–44 (1991)

薛定谔的猫(Schrödinger’s cat)是关于量子理论的一个理想实验。

尽管量子论的诞生已经过了一个世纪，其辉煌鼎盛与繁荣也过了半个世纪。但是量子理论曾经引起的困惑至今仍困惑着人们。正如玻尔的 名言：“谁要是第一次听到量子理论时没有感到困惑，那他一定没听懂。”薛定谔的猫是诸多量子困惑中有代表性的一个。这个猫十分可怜，她（假设这是一只雌性 的猫，以引起更多怜悯）被封在一个密室里，密室里有食物有毒药。毒药瓶上有一个锤子，锤子由一个电子开关控制，电子开关由放射性原子控制。如果原子核衰 变，则放出阿尔法粒子，触动电子开关，锤子落下，砸碎毒药瓶，释放出里面的氰化物气体，雌猫必死无疑。这个残忍的装置由薛定谔所 设计，所以雌猫便叫做薛定谔猫。原子核的衰变是随机事件，物理学家所能精确知道的只是半衰期——衰变一半所需要的时间。如果一种放射性元素的半衰期是一 天，则过一天，该元素就少了一半，再过一天，就少了剩下的一半。但是，物理学家却无法知道，它在什么时候衰变，上午，还是下午。当然，物理学家知道它在上 午或下午衰变的几率——也就是雌猫在上午或者下午死亡的几率。如果我们不揭开密室的盖子，根据我们在日常生活中的经验，可以认定，雌猫或者死，或者活。这 是她的两种本征态。但是，如果我们用薛定谔方程来描述薛定谔猫，则只能说，她处于一种活与不活的叠加态。我们只有在揭开盖子的一瞬间，才能确切地知道雌猫 是死是活。此时，猫的波函数由叠加态立即收缩到某一个本征态。量子理论认为：如果没有揭开盖子，进行观察，我们永远也不知道雌猫是死是活，她将永远到处于 半死不活的叠加态。这与我们的日常经验严重相违，要么死，要么活，怎么可能不死不活，半死半活？

薛定谔挖苦说：按照量子力学的解释，箱中之猫处于“死－活叠加态”——既死了又活着！要等到打开箱子看猫一眼才决定其生死。（请注意！不是发现而是决定，仅仅看一眼就足以致命！）正像哈姆雷特王子所说：“是死，还是活，这可真是一个问题。”只有当你打开盒子的时候，迭加态突然结束（在数学术语就是“坍缩（collapse）”），哈姆雷特王子的犹豫才终于结束，我们知道了猫的确定态：死，或者活。哥本哈根的几率诠释的优点是：只出现一个结果，这与我们观测到的结果相符合。但是有一个大的问题：它要求波函数突然坍缩。但物理学中没有一个公式能够描述这种坍缩。尽管如此，长期以来物理学家们出于实用主义的考虑，还是接受了哥本哈根的诠释。付出的代价是：违反了薛定谔方程。这就难怪薛定谔一直耿耿于怀了。

哥本哈根诠释在很长的一段时间成了“正统的”、“标准的”诠释。但那只不死不活的猫却总是像恶梦一样让物理学家们不得安宁。格利宾在《寻找薛定谔的猫》中想告诉我们的是，哥本哈根诠释在哪儿失败，以及用什么诠释可以替代它。

１９５７年，埃弗雷特提出的“多世界诠释”似乎为人们带来了福音，虽然由于它太离奇开始没有人认真对待。格利宾认为，多世界诠释有许多优点，由此它可以代替哥本哈根诠释。我们下面简单介绍一下埃弗雷特的多世界诠释。

格利宾在书中写道：“埃弗雷特……指出两只猫都是真实的。有一只活猫，有一只死猫，但它们位于不同的世界中。问题并不在于盒子中的放射性原子是否衰变，而 在于它既衰变又不衰变。当我们向盒子里看时，整个世界分裂成它自己的两个版本。这两个版本在其余的各个方面都是全同的。唯一的区别在于其中一个版本中，原 子衰变了，猫死了；而在另一个版本中，原子没有衰变，猫还活着。”

也就是说，上面说的“原子衰变了， 猫死了；原子没有衰变，猫还活着”这两个世界将完全相互独立地演变下去，就像两个平行的世界一样。格利宾显然十分赞赏这一诠释，所以他接着说：“这听起来 就像科幻小说，然而……它是基于无懈可击的数学方程，基于量子力学朴实的、自洽的、符合逻辑的结果。”“在量子的多世界中，我们通过参与而选择出自己的道 路。在我们生活的这个世界上，没有隐变量，上帝不会掷骰子，一切都是真实的。”按格利宾所说，爱因斯坦如果还活着，他也许会同意并大大地赞扬这一个“没有 隐变量，上帝不会掷骰子”的理论。

这个诠释的优点是：薛定谔方程始终成立，波函数从不坍缩，由此它简化了基本理论。它的问题是：设想过于离奇，付出的代价是这些平行的世界全都是同样真实的。这就难怪有人说：“在科学史上，多世界诠释无疑是目前所提出的最大胆、最野心勃勃的理论。”

 kNN分类算法是一种传统的基于统计的模式识别方法。算法思想很简单：对于一篇待分类文档，系统在训练集中找到k个最相近的邻居，使用这k个邻居的类别为 该文档的候选类别。该文档与k个邻居之间的相似度按类别分别求和，减去一个预先得到的截尾阈值，就得到该文档的类别测度。用kNN也表示所选k个最相近文 档的集合，公式（11-9）刻画了上述思想[Yang and Liu,1999]。

其 中，x为一篇待分类网页的向量表示；di为训练集中的一篇实例网页的向量表示；cj为一类别；（当d属于c}1,0{),(∈jicdyj时取1；当不属 于cdj时取0）；bj为预先计算得到的cj的最优截尾阈值；为待分类网页与网页实例之间的相似度，由文档间的余弦相似度公式（11-10）计算得到：

kNN算法本身简单有效，它是一种lazy-learning算法，分类器不需要使用训练集进行训练，训练时间复杂度为0。kNN分类的计算复杂度和训练集中的文档数目成正比，也就是说，如果训练集中文档总数为n，那么kNN的分类时间复杂度为O(n)。

KNN 需要人工分类一部分数据，例如代分类总数为4，则必须为每个分类寻找足够的样本，每个样本有人工分类。对于某个代分类文档，随机抽取n个邻居，n的计算需 要实际测试，选取合时的值，利用文档和这些邻居的相似关系，以及邻居的分类信息，得到该类的分类信息，寻找最大可能性的分类.

一． 贝叶斯过滤算法的基本步骤

1) 收集大量的垃圾邮件和非垃圾邮件，建立垃圾邮件集和非垃圾邮件集。
2) 提取邮件主题和邮件体中的独立字串例如 ABC32，￥234等作为TOKEN串并统计提取出的TOKEN串出现的次数即字频。按照上述的方法分别处理垃圾邮件集和非垃圾邮件集中的所有邮件。
3) 每一个邮件集对应一个哈希表，hashtable_good对应非垃圾邮件集而hashtable_bad对应垃圾邮件集。表中存储TOKEN串到字频的映射关系。
4) 计算每个哈希表中TOKEN串出现的概率P=（某TOKEN串的字频）/（对应哈希表的长度）
5) 综合考虑hashtable_good和hashtable_bad，推断出当新来的邮件中出现某个TOKEN串时，该新邮件为垃圾邮件的概率。数学表达式为：
A事件—-邮件为垃圾邮件;
t1,t2 …….tn代表TOKEN串
则P（A|ti）表示在邮件中出现TOKEN串ti时，该邮件为垃圾邮件的概率。
设
P1（ti）=（ti在hashtable_good中的值）
P2（ti）=（ti在hashtable_ bad中的值）
则 P（A|ti）= P1（ti）/[（P1（ti）+ P2（ti）]；
6) 建立新的哈希表 hashtable_probability存储TOKEN串ti到P（A|ti）的映射
7) 至此，垃圾邮件集和非垃圾邮件集的学习过程结束。根据建立的哈希表 hashtable_probability可以估计一封新到的邮件为垃圾邮件的可能性。
当新到一封邮件时，按照步骤2）生成TOKEN串。查询hashtable_probability得到该TOKEN 串的键值。
假设由该邮件共得到N个TOKEN串，t1,t2…….tn, hashtable_probability中对应的值为P1，P2，。。。。。。PN，
P(A|t1 ,t2, t3……tn)表示在邮件中同时出现多个TOKEN串t1,t2…….tn时，该邮件为垃圾邮件的概率。
由复合概率公式可得
P(A|t1 ,t2, t3……tn)=（P1*P2*。。。。PN）/[P1*P2*。。。。。PN+（1-P1）*（1-P2）*。。。（1-PN）]
当P(A|t1 ,t2, t3……tn)超过预定阈值时，就可以判断邮件为垃圾邮件。

二． 贝叶斯过滤算法举例

例如：一封含有“法轮功”字样的垃圾邮件 A
和 一封含有“法律”字样的非垃圾邮件B
根据邮件A生成hashtable_ bad，该哈希表中的记录为
法：1次
轮：1次
功：1次
计算得在本表中：
法出现的概率为0。3
轮出现的概率为0。3
功出现的概率为0。3
根据邮件B生成hashtable_good，该哈希表中的记录为：
法：1
律：1
计算得在本表中：
法出现的概率为0。5
律出现的概率为0。5
综合考虑两个哈希表，共有四个TOKEN串： 法 轮 功 律
当邮件中出现“法”时，该邮件为垃圾邮件的概率为：
P=0。3/（0。3+0。5）=0。375
出现“轮”时：
P=0。3/（0。3+0）=1
出现“功“时：
P=0。3/（0。3+0）=1
出现“律”时
P=0/（0+0。5）=0；
由此可得第三个哈希表：hashtable_probability 其数据为：
法：0。375
轮：1
功：1
律：0

当新到一封含有“功律”的邮件时，我们可得到两个TOKEN串，功 律
查询哈希表hashtable_probability可得
P（垃圾邮件| 功）=1
P （垃圾邮件|律）=0
此时该邮件为垃圾邮件的可能性为：
P=（0*1）/[0*1+（1-0）*（1-1）]=0
由此可推出该邮件为非垃圾邮件

From Wikipedia, the free encyclopedia

• Ten things you may not know about images on Wikipedia •

Jump to: navigation, search

In information theory and computer science, the Levenshtein distance is a string metric which is one way to measure edit distance. The Levenshtein distance between two strings is given by the minimum number of operations needed to transform one string into the other, where an operation is an insertion, deletion, or substitution of a single character. It is named after Vladimir Levenshtein, who considered this distance in 1965.^[1] It is useful in applications that need to determine how similar two strings are, such as spell checkers.

For example, the Levenshtein distance between “kitten” and “sitting” is 3, since these three edits change one into the other, and there is no way to do it with fewer than three edits:

1. kitten → sitten (substitution of ’s’ for ‘k’)
2. sitten → sittin (substitution of ‘i’ for ‘e’)
3. sittin → sitting (insert ‘g’ at the end)

It can be considered a generalization of the Hamming distance, which is used for strings of the same length and only considers substitution edits. There are also further generalizations of the Levenshtein distance that consider, for example, exchanging two characters as an operation, like in the Damerau-Levenshtein distance algorithm.

//

[edit] The algorithm

A commonly-used bottom-up dynamic programming algorithm for computing the Levenshtein distance involves the use of an (n + 1) × (m + 1) matrix, where n and m are the lengths of the two strings. This algorithm is based on the Wagner-Fischer algorithm for edit distance. Here is pseudocode for a function LevenshteinDistance that takes two strings, s of length m, and t of length n, and computes the Levenshtein distance between them:

int LevenshteinDistance(char s[1..m], char t[1..n])
   // d is a table with m+1 rows and n+1 columns
   declare int d[0..m, 0..n]

   for i from 0 to m
       d[i, 0] := i
   for j from 1 to n
       d[0, j] := j

   for i from 1 to m
       for j from 1 to n
           if s[i] = t[j] then cost := 0
                          else cost := 1
           d[i, j] := minimum(
                                d[i-1, j] + 1,     // deletion
                                d[i, j-1] + 1,     // insertion
                                d[i-1, j-1] + cost   // substitution
                            )

   return d[m, n]

Two examples of the resulting matrix (the minimum steps to be taken are highlighted):

The invariant maintained throughout the algorithm is that we can transform the initial segment s[1..i] into t[1..j] using a minimum of d[i,j] operations. At the end, the bottom-right element of the array contains the answer.

This algorithm is essentially part of a solution to the Longest common subsequence problem (LCS), in the particular case of 2 input lists.

[edit] Proof of correctness

As mentioned earlier, the invariant is that we can transform the initial segment s[1..i] into t[1..j] using a minimum of d[i,j] operations. This invariant holds since:

• It is initially true on row and column 0 because s[1..i] can be transformed into the empty string t[1..0] by simply dropping all i characters. Similarly, we can transform s[1..0] to t[1..j] by simply adding all j characters.
• The minimum is taken over three distances, each of which is feasible:
  • If we can transform s[1..i] to t[1..j-1] in k operations, then we can simply add t[j] afterwards to get t[1..j] in k+1 operations.
  • If we can transform s[1..i-1] to t[1..j] in k operations, then we can do the same operations on s[1..i] and then remove the original s[i] at the end in k+1 operations.
  • If we can transform s[1..i-1] to t[1..j-1] in k operations, we can do the same to s[1..i] and then do a substitution of t[j] for the original s[i] at the end if necessary, requiring k+cost operations.
• The operations required to transform s[1..n] into t[1..m] is of course the number required to transform all of s into all of t, and so d[n,m] holds our result.

This proof fails to validate that the number placed in d[i,j] is in fact minimal; this is more difficult to show, and involves an argument by contradiction in which we assume d[i,j] is smaller than the minimum of the three, and use this to show one of the three is not minimal.

[edit] Possible improvements

Possible improvements to this algorithm include:

• We can adapt the algorithm to use less space, O(m) instead of O(mn), since it only requires that the previous row and current row be stored at any one time.
• We can store the number of insertions, deletions, and substitutions separately, or even the positions at which they occur, which is always j.
• We can give different penalty costs to insertion, deletion and substitution.
• The initialization of d[i,0] can be moved inside the main outer loop.
• This algorithm parallelizes poorly, due to a large number of data dependencies. However, all the cost values can be computed in parallel, and the algorithm can be adapted to perform the minimum function in phases to eliminate dependencies.

[edit] Upper and lower bounds

The Levenshtein distance has several simple upper and lower bounds that are useful in applications which compute many of them and compare them. These include:

• It is always at least the difference of the sizes of the two strings.
• It is at most the length of the longer string.
• It is zero if and only if the strings are identical.
• If the strings are the same size, the Hamming distance is an upper bound on the Levenshtein distance.
• If the strings are called s and t, the number of characters (not counting duplicates) found in s but not in t is a lower bound.