{"id":607,"date":"2025-05-17T23:58:42","date_gmt":"2025-05-17T22:58:42","guid":{"rendered":"https:\/\/www.javaeinfacherkl\u00e4rt.de\/?p=607"},"modified":"2025-06-11T00:00:42","modified_gmt":"2025-06-10T23:00:42","slug":"myers-algorithmus-in-java-effizienter-vergleich-von-zeichenketten","status":"publish","type":"post","link":"https:\/\/www.xn--javaeinfacherklrt-4qb.de\/?p=607","title":{"rendered":"Myers&#8216; Algorithmus in Java: Effizienter Vergleich von Zeichenketten"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Einleitung<\/h2>\n\n\n\n<p>Beim Vergleich von Texten oder Zeichenketten ist es oft notwendig, die <strong>Differenz<\/strong> (Diff) zwischen zwei Strings zu ermitteln. Dies ist vor allem in Bereichen wie Versionskontrolle, Textverarbeitung, biologischer Sequenzanalyse oder Compilerbau relevant. Einer der effizientesten Algorithmen daf\u00fcr ist <strong>Myers\u2019 Algorithmus<\/strong>, der 1986 von <strong>Eugene W. Myers<\/strong> vorgestellt wurde. In diesem Artikel erl\u00e4utern wir den Algorithmus, sein Funktionsprinzip sowie eine exemplarische Implementierung in Java.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Problemstellung: Edit-Distance und Diff<\/h2>\n\n\n\n<p>Gegeben sind zwei Zeichenketten <code>A<\/code> und <code>B<\/code>. Ziel ist es, die minimalen \u00c4nderungen (Einf\u00fcgen, L\u00f6schen, Ersetzen) zu bestimmen, die notwendig sind, um aus <code>A<\/code> die Zeichenkette <code>B<\/code> zu erzeugen. Dies ist bekannt als <strong>Edit-Distanz<\/strong> oder <strong>Levenshtein-Distanz<\/strong>.<\/p>\n\n\n\n<p>Myers&#8216; Algorithmus geht einen Schritt weiter: Er liefert nicht nur die minimale Anzahl der \u00c4nderungen, sondern auch die konkrete Abfolge dieser \u00c4nderungen \u2013 also den <strong>Diff<\/strong>.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Grundprinzip von Myers\u2019 Algorithmus<\/h2>\n\n\n\n<p>Myers&#8216; Algorithmus basiert auf einem cleveren Traversieren eines <strong>2D-Gitters<\/strong>, das alle m\u00f6glichen Bearbeitungsschritte zwischen zwei Strings abbildet. Ziel ist es, den <strong>k\u00fcrzesten Pfad<\/strong> von der linken oberen Ecke (Start) zur rechten unteren Ecke (Ziel) zu finden.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Definitionen:<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>A.length = N<\/code><\/li>\n\n\n\n<li><code>B.length = M<\/code><\/li>\n\n\n\n<li>Ein <strong>Pfad<\/strong> durch das Gitter besteht aus folgenden Operationen:\n<ul class=\"wp-block-list\">\n<li><strong>Delete<\/strong> (nach unten gehen): entfernt ein Zeichen aus <code>A<\/code>.<\/li>\n\n\n\n<li><strong>Insert<\/strong> (nach rechts gehen): f\u00fcgt ein Zeichen zu <code>B<\/code> hinzu.<\/li>\n\n\n\n<li><strong>Diagonal (Match)<\/strong>: wenn <code>A[i] == B[j]<\/code>, bewegen wir uns diagonal nach rechts unten (kein Edit notwendig).<\/li>\n<\/ul>\n<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Optimierung:<\/h3>\n\n\n\n<p>Myers stellte fest, dass man den <strong>k\u00fcrzesten Pfad<\/strong> mit der geringsten Anzahl an Edits in Zeitkomplexit\u00e4t <strong>O(ND)<\/strong> finden kann, wobei <code>D<\/code> die minimale Anzahl von \u00c4nderungen ist. Zus\u00e4tzlich ben\u00f6tigt sein Algorithmus nur <strong>O(D\u00b2)<\/strong> Speicher \u2013 oder mit Modifikationen sogar <strong>O(N + M)<\/strong>.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Der Algorithmus Schritt f\u00fcr Schritt<\/h2>\n\n\n\n<p>Myers\u2019 Algorithmus verwendet eine Technik, bei der in jeder Iteration alle erreichbaren Positionen im Gitter f\u00fcr eine gegebene Edit-Distanz <code>d<\/code> \u00fcberpr\u00fcft werden.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Idee:<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>F\u00fcr jede Edit-Distanz <code>d<\/code> gibt es <code>2d + 1<\/code> m\u00f6gliche \u201eDiagonalen\u201c <code>k = -d, -d+2, ..., d-2, d<\/code><\/li>\n\n\n\n<li>F\u00fcr jedes <code>k<\/code> wird der weiteste Punkt <code>(x, y)<\/code> entlang der Diagonale bestimmt, an dem sich <code>A<\/code> und <code>B<\/code> weiter \u201ematchen\u201c lassen (sogenannter \u201eSnake\u201c).<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\">Datenstruktur:<\/h3>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Eine Map oder ein Array <code>V<\/code>, das f\u00fcr jede Diagonale <code>k<\/code> den gr\u00f6\u00dften <code>x<\/code>-Wert speichert, den man mit <code>d<\/code> \u00c4nderungen erreichen kann.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Java-Implementierung<\/h2>\n\n\n\n<p>Hier ist eine vereinfachte Java-Implementierung von Myers&#8216; Algorithmus, die eine Liste von Operationen (<code>Insert<\/code>, <code>Delete<\/code>, <code>Match<\/code>) zur\u00fcckgibt:<\/p>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-1\" data-shcb-language-name=\"JavaScript\" data-shcb-language-slug=\"javascript\"><span><code class=\"hljs language-javascript\"><span class=\"hljs-keyword\">import<\/span> java.util.*;\n\npublic <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">MyersDiff<\/span> <\/span>{\n\n    enum Operation {\n        INSERT, DELETE, MATCH\n    }\n\n    <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-class\"><span class=\"hljs-keyword\">class<\/span> <span class=\"hljs-title\">Edit<\/span> <\/span>{\n        Operation op;\n        int indexA;\n        int indexB;\n        char ch;\n\n        Edit(Operation op, int indexA, int indexB, char ch) {\n            <span class=\"hljs-keyword\">this<\/span>.op = op;\n            <span class=\"hljs-keyword\">this<\/span>.indexA = indexA;\n            <span class=\"hljs-keyword\">this<\/span>.indexB = indexB;\n            <span class=\"hljs-keyword\">this<\/span>.ch = ch;\n        }\n\n        public <span class=\"hljs-built_in\">String<\/span> toString() {\n            <span class=\"hljs-keyword\">return<\/span> op + <span class=\"hljs-string\">\" '\"<\/span> + ch + <span class=\"hljs-string\">\"' (A@\"<\/span> + indexA + <span class=\"hljs-string\">\", B@\"<\/span> + indexB + <span class=\"hljs-string\">\")\"<\/span>;\n        }\n    }\n\n    public <span class=\"hljs-keyword\">static<\/span> List&lt;Edit&gt; diff(<span class=\"hljs-built_in\">String<\/span> a, <span class=\"hljs-built_in\">String<\/span> b) {\n        int n = a.length();\n        int m = b.length();\n        int max = n + m;\n        <span class=\"hljs-built_in\">Map<\/span>&lt;Integer, Integer&gt; v = <span class=\"hljs-keyword\">new<\/span> HashMap&lt;&gt;();\n        <span class=\"hljs-built_in\">Map<\/span>&lt;<span class=\"hljs-built_in\">String<\/span>, Integer&gt; path = <span class=\"hljs-keyword\">new<\/span> HashMap&lt;&gt;();\n\n        v.put(<span class=\"hljs-number\">1<\/span>, <span class=\"hljs-number\">0<\/span>);\n\n        <span class=\"hljs-keyword\">for<\/span> (int d = <span class=\"hljs-number\">0<\/span>; d &lt;= max; d++) {\n            <span class=\"hljs-keyword\">for<\/span> (int k = -d; k &lt;= d; k += <span class=\"hljs-number\">2<\/span>) {\n                int x;\n                <span class=\"hljs-keyword\">if<\/span> (k == -d || (k != d &amp;&amp; v.get(k - <span class=\"hljs-number\">1<\/span>) &lt; v.get(k + <span class=\"hljs-number\">1<\/span>))) {\n                    x = v.get(k + <span class=\"hljs-number\">1<\/span>);\n                } <span class=\"hljs-keyword\">else<\/span> {\n                    x = v.get(k - <span class=\"hljs-number\">1<\/span>) + <span class=\"hljs-number\">1<\/span>;\n                }\n                int y = x - k;\n\n                <span class=\"hljs-comment\">\/\/ Snake: durchlaufen solange a&#91;x] == b&#91;y]<\/span>\n                <span class=\"hljs-keyword\">while<\/span> (x &lt; n &amp;&amp; y &lt; m &amp;&amp; a.charAt(x) == b.charAt(y)) {\n                    x++;\n                    y++;\n                }\n\n                v.put(k, x);\n                path.put(d + <span class=\"hljs-string\">\",\"<\/span> + k, x);\n\n                <span class=\"hljs-keyword\">if<\/span> (x &gt;= n &amp;&amp; y &gt;= m) {\n                    <span class=\"hljs-keyword\">return<\/span> backtrack(a, b, path, d);\n                }\n            }\n        }\n        <span class=\"hljs-keyword\">return<\/span> Collections.emptyList();\n    }\n\n    private <span class=\"hljs-keyword\">static<\/span> List&lt;Edit&gt; backtrack(<span class=\"hljs-built_in\">String<\/span> a, <span class=\"hljs-built_in\">String<\/span> b, <span class=\"hljs-built_in\">Map<\/span>&lt;<span class=\"hljs-built_in\">String<\/span>, Integer&gt; path, int d) {\n        List&lt;Edit&gt; edits = <span class=\"hljs-keyword\">new<\/span> ArrayList&lt;&gt;();\n        int x = a.length();\n        int y = b.length();\n\n        <span class=\"hljs-keyword\">for<\/span> (int i = d; i &gt; <span class=\"hljs-number\">0<\/span>; i--) {\n            int k = x - y;\n            int prevK = (k == -i || (k != i &amp;&amp; <span class=\"hljs-keyword\">get<\/span>(path, i - 1, k - 1) &lt; <span class=\"hljs-keyword\">get<\/span>(path, i - 1, k + 1)))\n                      ? k + 1 : k - 1;\n            int prevX = <span class=\"hljs-keyword\">get<\/span>(path, i - 1, prevK);\n            int prevY = prevX - prevK;\n\n            while (x &gt; prevX &amp;&amp; y &gt; prevY) {\n                x--;\n                y--;\n                edits.add(<span class=\"hljs-keyword\">new<\/span> Edit(Operation.MATCH, x, y, a.charAt(x)));\n            }\n\n            <span class=\"hljs-keyword\">if<\/span> (x == prevX) {\n                y--;\n                edits.add(<span class=\"hljs-keyword\">new<\/span> Edit(Operation.INSERT, x, y, b.charAt(y)));\n            } <span class=\"hljs-keyword\">else<\/span> {\n                x--;\n                edits.add(<span class=\"hljs-keyword\">new<\/span> Edit(Operation.DELETE, x, y, a.charAt(x)));\n            }\n        }\n\n        Collections.reverse(edits);\n        <span class=\"hljs-keyword\">return<\/span> edits;\n    }\n\n    private <span class=\"hljs-keyword\">static<\/span> int <span class=\"hljs-keyword\">get<\/span>(Map&lt;String, Integer&gt; map, int d, int k) {\n        <span class=\"hljs-keyword\">return<\/span> map.getOrDefault(d + <span class=\"hljs-string\">\",\"<\/span> + k, <span class=\"hljs-number\">0<\/span>);\n    }\n\n    public <span class=\"hljs-keyword\">static<\/span> <span class=\"hljs-keyword\">void<\/span> main(<span class=\"hljs-built_in\">String<\/span>&#91;] args) {\n        <span class=\"hljs-built_in\">String<\/span> a = <span class=\"hljs-string\">\"ABCABBA\"<\/span>;\n        <span class=\"hljs-built_in\">String<\/span> b = <span class=\"hljs-string\">\"CBABAC\"<\/span>;\n\n        List&lt;Edit&gt; edits = diff(a, b);\n        <span class=\"hljs-keyword\">for<\/span> (Edit e : edits) {\n            System.out.println(e);\n        }\n    }\n}\n<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-1\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">JavaScript<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">javascript<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<h3 class=\"wp-block-heading\">Beispielausgabe:<\/h3>\n\n\n<pre class=\"wp-block-code\" aria-describedby=\"shcb-language-2\" data-shcb-language-name=\"JavaScript\" data-shcb-language-slug=\"javascript\"><span><code class=\"hljs language-javascript\">DELETE <span class=\"hljs-string\">'A'<\/span> (A@<span class=\"hljs-number\">0<\/span>, B@<span class=\"hljs-number\">0<\/span>)\nDELETE <span class=\"hljs-string\">'B'<\/span> (A@<span class=\"hljs-number\">1<\/span>, B@<span class=\"hljs-number\">0<\/span>)\nMATCH <span class=\"hljs-string\">'C'<\/span> (A@<span class=\"hljs-number\">2<\/span>, B@<span class=\"hljs-number\">0<\/span>)\nMATCH <span class=\"hljs-string\">'A'<\/span> (A@<span class=\"hljs-number\">3<\/span>, B@<span class=\"hljs-number\">1<\/span>)\nMATCH <span class=\"hljs-string\">'B'<\/span> (A@<span class=\"hljs-number\">4<\/span>, B@<span class=\"hljs-number\">2<\/span>)\nINSERT <span class=\"hljs-string\">'A'<\/span> (A@<span class=\"hljs-number\">5<\/span>, B@<span class=\"hljs-number\">3<\/span>)\nMATCH <span class=\"hljs-string\">'B'<\/span> (A@<span class=\"hljs-number\">5<\/span>, B@<span class=\"hljs-number\">4<\/span>)\nDELETE <span class=\"hljs-string\">'A'<\/span> (A@<span class=\"hljs-number\">6<\/span>, B@<span class=\"hljs-number\">5<\/span>)\nMATCH <span class=\"hljs-string\">'C'<\/span> (A@<span class=\"hljs-number\">6<\/span>, B@<span class=\"hljs-number\">5<\/span>)\n<\/code><\/span><small class=\"shcb-language\" id=\"shcb-language-2\"><span class=\"shcb-language__label\">Code-Sprache:<\/span> <span class=\"shcb-language__name\">JavaScript<\/span> <span class=\"shcb-language__paren\">(<\/span><span class=\"shcb-language__slug\">javascript<\/span><span class=\"shcb-language__paren\">)<\/span><\/small><\/pre>\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Vorteile des Algorithmus<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Effizient<\/strong>: Besonders gut f\u00fcr lange Texte mit wenigen Unterschieden.<\/li>\n\n\n\n<li><strong>Optimal<\/strong>: Liefert den Pfad mit der <strong>minimalen Anzahl<\/strong> an \u00c4nderungen.<\/li>\n\n\n\n<li><strong>Speicherschonend<\/strong>: Mit Optimierungen auch speichereffizient.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Einsatzgebiete<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><strong>Git \/ diff-Tools<\/strong>: Myers&#8216; Algorithmus ist die Grundlage vieler <code>diff<\/code>-Implementierungen.<\/li>\n\n\n\n<li><strong>Texterkennung<\/strong>: Z.B. Rechtschreibpr\u00fcfung, Autovervollst\u00e4ndigung.<\/li>\n\n\n\n<li><strong>Biologische Sequenzanalyse<\/strong>: DNA-Alignment.<\/li>\n\n\n\n<li><strong>Compiler &amp; Parser<\/strong>: Fehlertolerante Analyse von Quellcode.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-alpha-channel-opacity\"\/>\n\n\n\n<h2 class=\"wp-block-heading\">Fazit<\/h2>\n\n\n\n<p>Myers&#8216; Algorithmus ist ein leistungsf\u00e4higer und eleganter Weg, um die Differenz zweier Zeichenketten zu berechnen. Die Java-Implementierung l\u00e4sst sich an zahlreiche Anwendungsf\u00e4lle anpassen und eignet sich hervorragend f\u00fcr den produktiven Einsatz. Wer sich tiefer mit Textvergleichen, Diff-Tools oder Edit-Distanzen besch\u00e4ftigt, sollte diesen Algorithmus unbedingt kennen und verstehen.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Einleitung Beim Vergleich von Texten oder Zeichenketten ist es oft notwendig, die Differenz (Diff) zwischen zwei Strings zu ermitteln. Dies ist vor allem in Bereichen wie Versionskontrolle, Textverarbeitung, biologischer Sequenzanalyse oder Compilerbau relevant. Einer der effizientesten Algorithmen daf\u00fcr ist Myers\u2019 Algorithmus, der 1986 von Eugene W. Myers vorgestellt wurde. In diesem Artikel erl\u00e4utern wir den [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[],"class_list":["post-607","post","type-post","status-publish","format-standard","hentry","category-plain_java"],"_links":{"self":[{"href":"https:\/\/www.xn--javaeinfacherklrt-4qb.de\/index.php?rest_route=\/wp\/v2\/posts\/607","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.xn--javaeinfacherklrt-4qb.de\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.xn--javaeinfacherklrt-4qb.de\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.xn--javaeinfacherklrt-4qb.de\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.xn--javaeinfacherklrt-4qb.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=607"}],"version-history":[{"count":1,"href":"https:\/\/www.xn--javaeinfacherklrt-4qb.de\/index.php?rest_route=\/wp\/v2\/posts\/607\/revisions"}],"predecessor-version":[{"id":608,"href":"https:\/\/www.xn--javaeinfacherklrt-4qb.de\/index.php?rest_route=\/wp\/v2\/posts\/607\/revisions\/608"}],"wp:attachment":[{"href":"https:\/\/www.xn--javaeinfacherklrt-4qb.de\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=607"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.xn--javaeinfacherklrt-4qb.de\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=607"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.xn--javaeinfacherklrt-4qb.de\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=607"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}