So bemerkt Google deine Tippfehler! Levenshtein Distanz einfach erklärt!
HTML-код
- Опубликовано: 7 июл 2024
- Inhalt 📚
Wenn man sich auf Google bei der Eingabe eines Suchbegriffs vertippt, bekommt man in der Regel vorgeschlagen, was man evtl. gemeint haben könnte. Doch woher weiß Google das? Nun, in diesemm Video erfährst du die Antwort. Wir werden uns dazu die Levenshtein-Distanz (Editierdistanz) anschauen.
Einführung 0:00
Problemstellung 0:26
Definition der Levenshtein-Distanz 1:48
Wie hilft Google diese Metrik? 3:40
Der Algorithmus 4:16
Beispiel 1 - ZELDA und ZELAD 5:16
Beispiel 2 - ZELDA und LINK 9:08
Aufgabe 11:28
EQUIPMENT(*)
🎤 Mikrofon amzn.to/3N0CHCL
✂️ Schnittprogramm amzn.to/3CZ217J
💻 Mein Laptop amzn.to/3ikMd5V
🖥️ Bildschirm amzn.to/3ig3yN5
SUPPORT
► Patreon / florian_dalwigk
► PayPal
► Unterstütze mich durch einen Kauf auf Amazon. Für dich entstehen keine Mehrkosten! (*) amzn.to/3LgyglY
SOCIAL MEDIA
💬 Discord: / discord
💡 Website: www.florian-dalwigk.de
📱 TikTok: / florian.dalwigk
🤳 Instagram: / florian.dalwigk
🐦 Twitter: / florian_dalwigk
📧 E-Mail: mailto:info@florian-dalwigk.de
📼 OK Google, wie funktioniert der PAGE RANK ALGORITHMUS? • OK Google, wie funktio...
Hier geht es zum Levenshtein-Tool 👉 phiresky.github.io/levenshtei...
(*) Bei den Amazon-Links (https.//amzn.to/???????) handelt es sich um Affiliate-Links. Wenn du etwas über diesen Link kaufst, bekomme ich eine kleine Provision. Der Preis ändert sich nicht, wenn du über diesen Link einkaufst. Vielen Dank für deine Unterstützung.
ACHTUNG! Bei 4:43 gibt es einen fiesen Tonfehler
Wollte gerade fragen, was da los ist und ob das bei anderen auch so ist...
Ganz ganz fies! Hätte mir beim Zeladschneiden fast in den Finger geschnibbelt
Dachte für eine kurze Zeit das meine Kopfhörer kaputt wären.
Hexerei, wie hast du dieses Bild als Kommentar gemacht?
😂
Hätte der Prof. das letztes Jahr nur annähernd so anschaulich erklärt.... Außerdem ärgere ich mich, dass ich das online Tool damals nicht kannte. Das hätte einem in der (open book) online Klausur einiges an Arbeit erspart.
Passend zum Prokrastinieren beim Lernen fürs Abitur :)
Sehr schön anschaulich erklärt! Bin grad sowieso dabei, all deine alten Algorithmen-Videos zu schauen für das Informatik-Abitur :)
Du bereicherst ganz RUclips mit deinen Videos!
Vielen Dank 😊
Super Video. Vielen Dank dass du das alles "um Sonst" für uns machst ♥
Gerne doch :) Ich freue mich, dass auch solche Themen bei euch Anklang finden.
*gratis umsonst wäre wen du nach dem Video so schlau wärst wie zuvor
Das war ein sehr gutes Video, danke dafür. Kommt wahrscheinlich auch dieses Semester in Algo 1 dran :)
Du bist deinem alten Namen mal wieder gerecht geworden!
Ich habe den Algorithmus verstanden!
Hervorragend :)
Auch ein alter Hase :D
:)
@@TheCelebreties Natürlich, ich hab ein Näschen für guten Content👌
Sehr cooles Video. Vielen Dank fürs Video
Danke für dein Feedback :)
Ich hab das zwar nicht gesucht, aber ich glaube das ist genau jetzt gerade hilfreich
Danke für das Video! Das ist genau mein Stoff gerade in der Uni :D
Mega :)
Das ist der Content den ich will
Sehr schönes Video. Hab mich schon länger mal gefragt wie dieser Algorithmus funktioniert. Hab es jetzt verstanden.
Perfekt 😁
Die Realität ist dann aber doch noch ein bisschen komplexer ;)
@@Florian.Dalwigk also war speziell bezogen auf levenshtein gemeint, da ich das mal in einem Programm als Bibliothek genutzt habe, allerdings keine Ahnung hatte wie und warum es funktioniert.
Ah, OK
4:43 Da musste ich ganz kurz einen minimalen Herzinfarkt erleiden aus Schreck
Sehr interessant und hervorragend erklärt meiner Meinung nach! Aber wieso funktioniert der Algorithmus genau so, wie er funktioniert?
Na hoppla
Die Antwort auf die Frage am Ende des Videos ist folgende: Man löscht das Z und das E von Zelda. Das L ist dann am Anfang und man ersetzt das D durch I und das A durch ein N. Abschliessend fügt man noch das K hinzu und hat somit 5 Steps benötigt.
Danke für dieses Aufschlussreiche Video.
EDITED: Und die Lösung zur Aufgabe ganz am Ende wäre Folgende:
Ich habe mit meiner Tabelle eine Levenshtein Distanz von 5 erhalten. Dies scheint aber falsch zu sein und die Distanz ist 3.
1. L einfügen zwischen A und G
2. 1 durch ein I ersetzen
3. Eines der Beiden U's entfernen
Sehr cooles video und Gott sei dank einfach erklärt XD
Dachte bei Minute 4:50 schon meine Lautsprecher sind defekt😅
same xd erstmal Kabel gecheckt ob das richtig drin ist
Super Video
Vielen Dank 😊
genau die art von videos die ich am meisten mag😎
Das freut mich!
+1
Super Video👩💻
Dankeschön 😊
based pic
Mega!
Danke :)
wieder passiv in meiner Freizeit Informatik gelernt 😎
Yay 😁
so ein nices video! wirklich. sehr hilfreich, gerne mehr davon
Vielen Dank :)
Mit wie vielen Wörtern wird das eingegebene Wort bei dem Suchalgorithmus von Google verglichen um die kürzeste Levenshtein Distanz zu berechnen? Wird bei eingegebenen Sätzen auch Wort für Wort vorgegangen um die Levenshtein-Distanz zu bestimmen oder werden in diesem Fall die Levenshtein-Distanz gleich für ganze Sätze ermittelt?
Antwort ist 2, wenn ich mich nicht verguckt habe!😇 Eine Löschung und eine Ersetzung!
Ohne zu wiesen wie es heißt schon dutzende male genutzt!
Mit'nem nested for-loop easiest durch beide char-arrays ackern und dabei noch so schön effektiv, nice dieser "Levenshtein-Distanz"-Algorithmus!👍
Dankeschön!😁👍👍👍🤟😎
Edit:
Oh ne, 3, hab das l nicht gecheckt...!🙈🙉🙊
...nem Script wäre das nicht passiert!😂😂😂
Sehr interessant. 👍👍👍
Bei 4:43 bin ich erschrocken obwohl ich drauf gewartet hab 😂.
Danke dir 😊
Sorry, ich hab das beim Schneiden nicht gemerkt ... Das muss beim Rendern passiert sein.
Wieso hast du auf einen Tonfehler gewartet? O.o Oder ist das ein Insider? xd
Siehe angepinnten Kommentar.
@@Florian.Dalwigk Ah, danke. 👍
Algorithmen verstehen!
Anhand einer ruhigen, eloquenten Stimme und sehr treffenden Analogien 💜
Hast du die Vertonung bei der Tabellenerklärung aus den immer wieder seinen "Soundblöcken" zusammengeschnitten oder gar automatisiert oder wirklich alles x-mal eingesprochen?
Das ist glaube ich das erste Mal, dass ich deinen Charakter ohne Brille sehe.
😅
In Herne lebt man gerne, das ist die Einkaufsstadt mit Herz!
Gutes Video! Unser Prof hat uns letztens eigentlich nur ganz nebenbei von diesem Algorithmus erzählt. Der hat mich dann näher interessiert und schon kommst du damit um die Ecke !😅 Wusstest du, dass man diesen Algorithmus auch zu Handschrifterkennung auf Tablets und co verwenden kann ?
Jep :)
super wie immer! Deine uploadrate ist wirklich hoch! hast du vor auch noch zu schlafen ???😂
...Ehrlich gesagt fand ich den Teil mit den tabellen ein bisschen langwierig
;)
Geiel! 😄
Tolles Video und mega gut erklärt 😎 heißer Dank 🤘
Kein Wunder, dass Deine Vids in Schulen verwendung finden 🌹
Wem es in der Mitte zu lang war, soll Vorspulen 😁
Btw.: Ich hatte noch nie von dieser Methode gehört, mich aber schon oft gefragt, wie G zu teils echt kruden Vorschlägen kommt 😂🤣😂
11:41, livingstein distance (im kopf 2), weil man einmal die 1 durch das "i" ersetzen muss und das "u" löschen muss
fast, du musst bei dem 2. Wort noch ein "l" zwischen dem "A" und dem "g" einsetzen.
somit kommst du auf eine Levenshtein-Distanz von 3
Man kann hier nichts „ersetzen“ das ist „löschen“ und „einfügen“, deswegen ist die distanz 4
@@CrackedPi hatte ich auch gedacht. Aber der online calculator sagt auch "replace" und spuckt als Ergebnis eine 3 aus
@@CrackedPi Weshalb kann man nichts "ersetzen"?
Weil "ersetzen" aus den beiden Elementaroperationen "löschen" und "einfügen" besteht.
Lustig, genau den Algorithmus musste ich für ein Seminar auch programmieren. Bioinformatik.
👍
@@Florian.Dalwigk Der Algorithmus wurde dort auch eingeführt um genetische Ähnlichkeiten zu berechnen. Dort bekamen die 3 Operationen dann teilweise auch andere Gewichtungen, je nach dem wie wahrscheinlich diese Mutationen in der Natur zu finden sind. Aber die genauen Zahlen habe ich leider nicht mehr im Kopf, ist leider schon eine weile her...
Klingt ziemlich spannend :)
Hätte niemals gedacht, dass unser Brake mal in einem YT Video erwähnt wird. Ich habe mal „Körriwurst“ eingegeben. Leider gibt es bereits ein Produkt mit dem Namen. Allerdings wurde in den Suchvorschlägen unterhalb dann die „Currywurst“ erwähnt.
Haha, noch ein Braker :)
1:13 Ich als Braker freue mich, dass du meine Heimatstadt als Beispiel genommen hast😆
Nice! Ich habe mich schon gefragt, wie viele Braker unter meinen Zuschauern sind ;)
Jup damit hatte ich schon mal zu tun. Hab dann noch am ende die distanz um die halbe länge beider wörter geteilt. So ergibt sich das hi erund ei sich mehr unterscheiden als Tastatur und Tastatrur
Interessant wäre noch die Frage wo das zweite Wort herkommt. Wenn ich mich vertippe steht da ja nur ein Wort. Wird da dann für jedes Wort in einem Wörterbuch die Levenshtein Distanz berechnet? Bei der Frage am Ende hätte ich auf eine 4 als Lösing getippt weil am Anfang ja erklärt wurde, dass es kein replace gibt. Aber der online calculator sagt 3.
l einfügen, 1 austauschen und e entfernen. Sind 3 Operationen. man darf keine Buchstaben vertauschen, aber das ersetzen ist erlaubt.
Ersetzen geht, aber nicht zwei Buchstaben vertauschen. Also: L löschen, I durch 1 ersetzen, U löschen. Drei Operationen.
@@Lovuschka Das L ist doch gleich. das muss nicht gelöscht werden.
es sind nur 2 Operationen nötig.
I durch 1 ersetzen und U hinzufügen
oder umgekehrt: 1 durch I ersetzen und U löschen
@@p-196 schau nochmal hin, da fehlt ein kleines L, es sind schon 3 Operationen ;)
Da man zwei Wörter benötigt um die levenshtein Distanz zu ermitteln Frage ich mich wie Google überhaupt auf die Vergleichswörter kommt. Denn ich verstehe zwar den Algorithmus aber nicht wie er letztendlich implementiert würde
Apropos: gibt es so einen Algorithmus vielleicht vorgefertigt(egal in welcher Sprache) mit Tastaturlayouts? D.h. dass man zwei Strings und ein Tastaturlayout übergibt und die Funktion einem zurückliefert wieviele Tasten Abweichung die beiden Strings haben?
Bestimmt. Ich hab das aber noch nicht gesehen.
Die kam bei uns im Informatik-Studium nicht dran. Dafür jede andere Metrik, die man aus der Analysis 2, Lineare Algebra 1/2 und Numerik kennt. Schade...
Als ich Dij sah hatte ich meine "Datenstrukturen und Algorithmen" im Kopf. Das beste ich bringe seit 4 Jahren den leuten "DuA" bei und bin durch die Klausur gefallen 2x. Warum: naja einfach viel zu wenig zeit. 20 sortieralgorithmen bei jedem sortiervorgang zu bezeichen am ende dynamisch was zu "entwickeln" etc. da fehlten allen am ende die zeit
unten L nach Oben R -> das klingt nach Knappsack oder wie man das auch nennt
PSS: müsste 4 sein als result
Warum nur hat mir unser Mathelehrer die Dinge nie so anschaulich erklärt?
Wenn man morgens vor der Arbeit bei einer Tasse Kaffee erstmal das Gehirn einschaltet 😁 danke dafür! Nun bin ich fit für den Tag!
Perfekt 😁 Alles Gute!
Cool
😎
ruclips.net/video/bMahFqT6XPQ/видео.html
Es gibt an dieser Stelle ein Soundproblem
Ich wünschte, die Autovervollständigung meiner IDE wäre auch so schlau wie Google :D
😁👍
ZELDA -> LELDA -> LILDA -> LINDA -> LINKA -> LINK
L von den beiden Strings am Ende sollte 3 sein, wenn ich mich nicht vertan habe.
Tolles Video, vielen Dank für die genialen Mathe/Informatik Exkurse!
6:50 Wie kompliziert willst du es denn noch erklären?
Was meinst du genau? Wo hakt es?
diesemm -> diesem hat eine Levenshtein-Distanz von 1, wieso kann Google das nicht korrigieren lol (Tippfehler in der Videobeschreibung)
👍
👍
-Z
-E
D durch I ersetzen
A durch N ersetzen
K anfügen
Wie man Zelda in Link überführt? Z zu L, E zu I, L zu N, D zu K und A löschen.
Ich hätte eine Levenshtein Distanz von 4 gesagt: ein l hinzufügen, die 1 mit i vertauschen und das u entfernen
3:30 Man sieht auch schön, dass man direkt von ZELA auf ZELDA kommen könnte.
Wo bleibt denn die Python Implementierung?
Siehe Hashtag des Videos ;)
Hier ging es um die Erklärung des Algorithmus!
@@Florian.Dalwigk kommt denn noch eins zur Implementierung?
Möglich, allerdings gibt es dazu bereits zahlreiche Implementierungen.
Kurz bei 4:43 erschrocken
Sorry, ich sollte eine Triggerwarnung einfügen!
Google macht das definitiv anders, das wurde ganz früher mal so gemacht, dann wurde das Tastaturlayout dazu gezogen und heute ML 👨💻
ZELDA - (1)ELDA - (2)LDA -(3)LIA - (4)LIN - (5)LINK
Der Arm im Thumbnail sieht irgendwie nicht Gesund aus xD, nettes Video
😅😁👍
Wenn ich mir vorstelle, dass dieser Algorithmus von jemanden erfunden wurde, wird mir ganz schnell komisch...
Wieso?
man könnte auch das A löschen und anschließend ein A am Ende einfügen
ZELAD -> ZELD -> ZELDA
11:35
Antwort auf gestellte Frage:
Ich hätte spontan 10 gesagt
Der Drachenlord sagt auch immer Zelad ....^^
😏
Bride of the Wind
Bin ich der einzige der bei 4:43 so ein komisches Geräusch hört?
Definitiv nein 😅
Ich habe 3 raus falls ich mich nicht verrechnet habe
Antwort zur Aufgabe: Levenshtein Distanz = 2
Beim zweiten fehlt l, ist 1 statt i und ein u zu viel
3 mindestens
3
2
5 ist logisch 4* tauschen 1* hinzufügen.
Ab die 9* klugen ja auch 4* tauschen einmal abziehen währe richtig gewesen. PS erster dem das auffällt 😀
In diesem Video maximale Gewalt. Ein Sechstel von Brakel wird ausgelöscht.
😂
Google macht aber noch viel mehr, Google Mal Zoo Sammlung, bei mir gibt es sofort Anno 1800 Zoo Sets, bei euch denke ich ehr nicht. Google merkt sich was ihr sucht.
Es ist eben stark vereinfacht dargestellt, um ein Praxisbeispiel zu haben.
@@Florian.Dalwigk alles gut, wollte damit nur auf den praktischen Nutzen hinweisen, das manche Konzerne so viel über uns wissen.
Es wird ja immer so viel gemeckert, aber hätte wir das nicht, würden wir uns fragen warum Google das bei der 1000 Suche nach ein und dem selben immer noch nicht kapiert hat.
Herne Ultras wo seid ihr!!!!
😂
Die Levenshtein Distanz zwischen "Algorithmus" und "Algor1thmuus" beträgt 2
Berechnung:
S 11 10 9 8 7 6 6 5 4 3 2 2 2
U 10 9 8 7 6 5 5 4 3 2 1 2 3
M 9 8 7 6 5 4 4 3 2 1 2 3 4
H 8 7 6 5 4 3 3 2 1 2 3 4 5
T 7 6 5 4 3 2 2 1 2 3 4 5 6
I 6 5 4 3 2 1 1 2 3 4 5 6 7
R 5 4 3 2 1 0 1 2 3 4 5 6 7
O 4 3 2 1 0 1 2 3 4 5 6 7 8
G 3 2 1 0 1 2 3 4 5 6 7 8 9
L 2 1 0 1 2 3 4 5 6 7 8 9 10
A 1 0 1 2 3 4 5 6 7 8 9 10 11
0 1 2 3 4 5 6 7 8 9 10 11 12
A L G O R 1 T H M U U S
Ich hoffe, RUclips stellt das hier jetzt richtig dar.
Yes :) Super gelöst und toll dargestellt!
@@Florian.Dalwigk hab das ganze in Open Office Calc gemacht :)
😊👍
Das ist zwar richtig, aber waren die gegebenen Zeichenketten nicht Algorithmus und Agor1thmuus? Bei den beiden finde ich keine Möglichkeit unter 3. Deswegen war ich erst einmal über deine Antwort verwirrt.
@@caluthan i durch 1 ersetzen und u hinzufügen
Hab' mir dazu schonmal eine Funktion in Lua geschrieben. Output der Aufgabe: 8
epic
👌
Bitte kein Clickbait 😭
?
Wenn der Inhalt doch passt ...
@@Florian.Dalwigk Ja, ich hab halt was mit Link erwartet oder zu Gaming. 😢
Naja, es geht doch u. a. um Zelda. Außerdem steht doch auch im Titel, um was es geht ;)
@@Florian.Dalwigk Aber es geht doch nur um Zelda, weil du dir das Wort ausgesucht hast. Und bei dem Wort geht es nur um die Buchstabenkombination und nicht die Semantik. Es hätte also jedes beliebige Wort sein können.
Ich dachte das Video war an Leute gerichtet, die nicht wissen, was sich hinter der Levenshtein Distanz verbirgt. Sonst müsste man es ja auch nicht erklären. Ich hatte dabei eher an Navigation im Spiel oder Zielen mit Pfeilen gedacht, aber das liegt natürlich auch an mir und soll nicht die Allgemeinheit widerspiegeln.
Also wenn das Titelbild zu 0% locken sollte, dann nehme ich das natürlich zurück. Ich danke dir so oder so für das tolle Video und wollte nur vermeiden, dass du abdriftest! ❤️ Keep up the good work!
zweiter edit: doch erster xD
Edit Edit: Nein ;)
Wow heftig.
Mal kein JulienDumm Fanboy Video 👍👍👍
Das sind doch mal wieder interessante Videos.
Popokriechen bei Julien hast du nicht nötig