Calculate Levenshtein distance between two strings in Python





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ margin-bottom:0;
}







11












$begingroup$


I need a function that checks how different are two different strings. I chose the Levenshtein distance as a quick approach, and implemented this function:



from difflib import ndiff

def calculate_levenshtein_distance(str_1, str_2):
"""
The Levenshtein distance is a string metric for measuring the difference between two sequences.
It is calculated as the minimum number of single-character edits necessary to transform one string into another
"""
distance = 0
buffer_removed = buffer_added = 0
for x in ndiff(str_1, str_2):
code = x[0]
# Code ? is ignored as it does not translate to any modification
if code == ' ':
distance += max(buffer_removed, buffer_added)
buffer_removed = buffer_added = 0
elif code == '-':
buffer_removed += 1
elif code == '+':
buffer_added += 1
distance += max(buffer_removed, buffer_added)
return distance


Then calling it as:



similarity = 1 - calculate_levenshtein_distance(str_1, str_2) / max(len(str_1), len(str_2))


How sloppy/prone to errors is this code? How can it be improved?










share|improve this question









New contributor




Kyra_W is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.







$endgroup$



















    11












    $begingroup$


    I need a function that checks how different are two different strings. I chose the Levenshtein distance as a quick approach, and implemented this function:



    from difflib import ndiff

    def calculate_levenshtein_distance(str_1, str_2):
    """
    The Levenshtein distance is a string metric for measuring the difference between two sequences.
    It is calculated as the minimum number of single-character edits necessary to transform one string into another
    """
    distance = 0
    buffer_removed = buffer_added = 0
    for x in ndiff(str_1, str_2):
    code = x[0]
    # Code ? is ignored as it does not translate to any modification
    if code == ' ':
    distance += max(buffer_removed, buffer_added)
    buffer_removed = buffer_added = 0
    elif code == '-':
    buffer_removed += 1
    elif code == '+':
    buffer_added += 1
    distance += max(buffer_removed, buffer_added)
    return distance


    Then calling it as:



    similarity = 1 - calculate_levenshtein_distance(str_1, str_2) / max(len(str_1), len(str_2))


    How sloppy/prone to errors is this code? How can it be improved?










    share|improve this question









    New contributor




    Kyra_W is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
    Check out our Code of Conduct.







    $endgroup$















      11












      11








      11


      2



      $begingroup$


      I need a function that checks how different are two different strings. I chose the Levenshtein distance as a quick approach, and implemented this function:



      from difflib import ndiff

      def calculate_levenshtein_distance(str_1, str_2):
      """
      The Levenshtein distance is a string metric for measuring the difference between two sequences.
      It is calculated as the minimum number of single-character edits necessary to transform one string into another
      """
      distance = 0
      buffer_removed = buffer_added = 0
      for x in ndiff(str_1, str_2):
      code = x[0]
      # Code ? is ignored as it does not translate to any modification
      if code == ' ':
      distance += max(buffer_removed, buffer_added)
      buffer_removed = buffer_added = 0
      elif code == '-':
      buffer_removed += 1
      elif code == '+':
      buffer_added += 1
      distance += max(buffer_removed, buffer_added)
      return distance


      Then calling it as:



      similarity = 1 - calculate_levenshtein_distance(str_1, str_2) / max(len(str_1), len(str_2))


      How sloppy/prone to errors is this code? How can it be improved?










      share|improve this question









      New contributor




      Kyra_W is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.







      $endgroup$




      I need a function that checks how different are two different strings. I chose the Levenshtein distance as a quick approach, and implemented this function:



      from difflib import ndiff

      def calculate_levenshtein_distance(str_1, str_2):
      """
      The Levenshtein distance is a string metric for measuring the difference between two sequences.
      It is calculated as the minimum number of single-character edits necessary to transform one string into another
      """
      distance = 0
      buffer_removed = buffer_added = 0
      for x in ndiff(str_1, str_2):
      code = x[0]
      # Code ? is ignored as it does not translate to any modification
      if code == ' ':
      distance += max(buffer_removed, buffer_added)
      buffer_removed = buffer_added = 0
      elif code == '-':
      buffer_removed += 1
      elif code == '+':
      buffer_added += 1
      distance += max(buffer_removed, buffer_added)
      return distance


      Then calling it as:



      similarity = 1 - calculate_levenshtein_distance(str_1, str_2) / max(len(str_1), len(str_2))


      How sloppy/prone to errors is this code? How can it be improved?







      python edit-distance






      share|improve this question









      New contributor




      Kyra_W is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.











      share|improve this question









      New contributor




      Kyra_W is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      share|improve this question




      share|improve this question








      edited 2 days ago









      Reinderien

      5,445927




      5,445927






      New contributor




      Kyra_W is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.









      asked 2 days ago









      Kyra_WKyra_W

      585




      585




      New contributor




      Kyra_W is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.





      New contributor





      Kyra_W is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






      Kyra_W is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
      Check out our Code of Conduct.






















          2 Answers
          2






          active

          oldest

          votes


















          14












          $begingroup$

          There is a module available for exactly that calculation, python-Levenshtein. You can install it with pip install python-Levenshtein.



          It is implemented in C, so is probably faster than anything you can come up with yourself.



          from Levenshtein import distance as levenshtein_distance




          According to the docstring conventions, your docstring should look like this, i.e. with the indentation aligned to the """ and the line length curtailed to 80 characters.



          def calculate_levenshtein_distance(str_1, str_2):
          """
          The Levenshtein distance is a string metric for measuring the difference
          between two sequences.
          It is calculated as the minimum number of single-character edits necessary to
          transform one string into another.
          """
          ...





          share|improve this answer











          $endgroup$









          • 10




            $begingroup$
            Just to note the module is licensed under GPL 2.0 so watch out if you're using it for work.
            $endgroup$
            – lucasgcb
            2 days ago










          • $begingroup$
            Just to point out a small nitpick to other people who may stumble upon this answer, as per help center: "Every answer must make at least one insightful observation about the code in the question. Answers that merely provide an alternate solution with no explanation or justification do not constitute valid Code Review answers and may be deleted." While this answer does provide alternative and existing module suggestion, it also goes into some suggestions about improving code quality. So it's an example of a decent answer
            $endgroup$
            – Sergiy Kolodyazhnyy
            2 days ago










          • $begingroup$
            Thanks! I did not know of this module. Will check it out
            $endgroup$
            – Kyra_W
            yesterday






          • 1




            $begingroup$
            @SergiyKolodyazhnyy While I (obviously) agree, and that is one of the reasons I added that part, I would actually argue that "It is implemented in C, so is probably faster than anything you can come up with yourself" would get around the "no explanation or justification" clause
            $endgroup$
            – Graipher
            yesterday





















          9












          $begingroup$

          The code itself is rather clear. There are some smaller changes I would make



          tuple unpacking



          You can use tuple unpacking to do:



          for code, *_ in ndiff(str1, str2):


          instead of:



          for x in ndiff(str_1, str_2):
          code = x[0]


          dict results:



          Instead of a counter for the additions and removals, I would keep it in 1 dict: counter = ({"+": 0, "-": 0})



          def levenshtein_distance(str1, str2, ):
          counter = {"+": 0, "-": 0}
          distance = 0
          for edit_code, *_ in ndiff(str1, str2):
          if edit_code == " ":
          distance += max(counter.values())
          counter = {"+": 0, "-": 0}
          else:
          counter[edit_code] += 1
          distance += max(counter.values())
          return distance


          generators



          A smaller, less useful variation, is to let this method be a generator, and use the builtin sum to do the summary. this saves 1 variable inside the function:



          def levenshtein_distance_gen(str1, str2, ):
          counter = {"+": 0, "-": 0}
          for edit_code, *_ in ndiff(str1, str2):
          if edit_code == " ":
          yield max(counter.values())
          counter = {"+": 0, "-": 0}
          else:
          counter[edit_code] += 1
          yield max(counter.values())

          sum(levenshtein_distance_gen(str1, str2))




          timings



          The differences in timings between the original and both these variations are minimal, and within the variation of results. This is rather logical, since for simple strings (aaabbbc and abcabcabc) 90% of the time is spent in ndiff






          share|improve this answer









          $endgroup$













          • $begingroup$
            Awesome suggestions. I had not even considered the generator approach, but it looks very nice. Thanks
            $endgroup$
            – Kyra_W
            yesterday












          Your Answer





          StackExchange.ifUsing("editor", function () {
          return StackExchange.using("mathjaxEditing", function () {
          StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
          StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
          });
          });
          }, "mathjax-editing");

          StackExchange.ifUsing("editor", function () {
          StackExchange.using("externalEditor", function () {
          StackExchange.using("snippets", function () {
          StackExchange.snippets.init();
          });
          });
          }, "code-snippets");

          StackExchange.ready(function() {
          var channelOptions = {
          tags: "".split(" "),
          id: "196"
          };
          initTagRenderer("".split(" "), "".split(" "), channelOptions);

          StackExchange.using("externalEditor", function() {
          // Have to fire editor after snippets, if snippets enabled
          if (StackExchange.settings.snippets.snippetsEnabled) {
          StackExchange.using("snippets", function() {
          createEditor();
          });
          }
          else {
          createEditor();
          }
          });

          function createEditor() {
          StackExchange.prepareEditor({
          heartbeatType: 'answer',
          autoActivateHeartbeat: false,
          convertImagesToLinks: false,
          noModals: true,
          showLowRepImageUploadWarning: true,
          reputationToPostImages: null,
          bindNavPrevention: true,
          postfix: "",
          imageUploader: {
          brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
          contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
          allowUrls: true
          },
          onDemand: true,
          discardSelector: ".discard-answer"
          ,immediatelyShowMarkdownHelp:true
          });


          }
          });






          Kyra_W is a new contributor. Be nice, and check out our Code of Conduct.










          draft saved

          draft discarded


















          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217065%2fcalculate-levenshtein-distance-between-two-strings-in-python%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown

























          2 Answers
          2






          active

          oldest

          votes








          2 Answers
          2






          active

          oldest

          votes









          active

          oldest

          votes






          active

          oldest

          votes









          14












          $begingroup$

          There is a module available for exactly that calculation, python-Levenshtein. You can install it with pip install python-Levenshtein.



          It is implemented in C, so is probably faster than anything you can come up with yourself.



          from Levenshtein import distance as levenshtein_distance




          According to the docstring conventions, your docstring should look like this, i.e. with the indentation aligned to the """ and the line length curtailed to 80 characters.



          def calculate_levenshtein_distance(str_1, str_2):
          """
          The Levenshtein distance is a string metric for measuring the difference
          between two sequences.
          It is calculated as the minimum number of single-character edits necessary to
          transform one string into another.
          """
          ...





          share|improve this answer











          $endgroup$









          • 10




            $begingroup$
            Just to note the module is licensed under GPL 2.0 so watch out if you're using it for work.
            $endgroup$
            – lucasgcb
            2 days ago










          • $begingroup$
            Just to point out a small nitpick to other people who may stumble upon this answer, as per help center: "Every answer must make at least one insightful observation about the code in the question. Answers that merely provide an alternate solution with no explanation or justification do not constitute valid Code Review answers and may be deleted." While this answer does provide alternative and existing module suggestion, it also goes into some suggestions about improving code quality. So it's an example of a decent answer
            $endgroup$
            – Sergiy Kolodyazhnyy
            2 days ago










          • $begingroup$
            Thanks! I did not know of this module. Will check it out
            $endgroup$
            – Kyra_W
            yesterday






          • 1




            $begingroup$
            @SergiyKolodyazhnyy While I (obviously) agree, and that is one of the reasons I added that part, I would actually argue that "It is implemented in C, so is probably faster than anything you can come up with yourself" would get around the "no explanation or justification" clause
            $endgroup$
            – Graipher
            yesterday


















          14












          $begingroup$

          There is a module available for exactly that calculation, python-Levenshtein. You can install it with pip install python-Levenshtein.



          It is implemented in C, so is probably faster than anything you can come up with yourself.



          from Levenshtein import distance as levenshtein_distance




          According to the docstring conventions, your docstring should look like this, i.e. with the indentation aligned to the """ and the line length curtailed to 80 characters.



          def calculate_levenshtein_distance(str_1, str_2):
          """
          The Levenshtein distance is a string metric for measuring the difference
          between two sequences.
          It is calculated as the minimum number of single-character edits necessary to
          transform one string into another.
          """
          ...





          share|improve this answer











          $endgroup$









          • 10




            $begingroup$
            Just to note the module is licensed under GPL 2.0 so watch out if you're using it for work.
            $endgroup$
            – lucasgcb
            2 days ago










          • $begingroup$
            Just to point out a small nitpick to other people who may stumble upon this answer, as per help center: "Every answer must make at least one insightful observation about the code in the question. Answers that merely provide an alternate solution with no explanation or justification do not constitute valid Code Review answers and may be deleted." While this answer does provide alternative and existing module suggestion, it also goes into some suggestions about improving code quality. So it's an example of a decent answer
            $endgroup$
            – Sergiy Kolodyazhnyy
            2 days ago










          • $begingroup$
            Thanks! I did not know of this module. Will check it out
            $endgroup$
            – Kyra_W
            yesterday






          • 1




            $begingroup$
            @SergiyKolodyazhnyy While I (obviously) agree, and that is one of the reasons I added that part, I would actually argue that "It is implemented in C, so is probably faster than anything you can come up with yourself" would get around the "no explanation or justification" clause
            $endgroup$
            – Graipher
            yesterday
















          14












          14








          14





          $begingroup$

          There is a module available for exactly that calculation, python-Levenshtein. You can install it with pip install python-Levenshtein.



          It is implemented in C, so is probably faster than anything you can come up with yourself.



          from Levenshtein import distance as levenshtein_distance




          According to the docstring conventions, your docstring should look like this, i.e. with the indentation aligned to the """ and the line length curtailed to 80 characters.



          def calculate_levenshtein_distance(str_1, str_2):
          """
          The Levenshtein distance is a string metric for measuring the difference
          between two sequences.
          It is calculated as the minimum number of single-character edits necessary to
          transform one string into another.
          """
          ...





          share|improve this answer











          $endgroup$



          There is a module available for exactly that calculation, python-Levenshtein. You can install it with pip install python-Levenshtein.



          It is implemented in C, so is probably faster than anything you can come up with yourself.



          from Levenshtein import distance as levenshtein_distance




          According to the docstring conventions, your docstring should look like this, i.e. with the indentation aligned to the """ and the line length curtailed to 80 characters.



          def calculate_levenshtein_distance(str_1, str_2):
          """
          The Levenshtein distance is a string metric for measuring the difference
          between two sequences.
          It is calculated as the minimum number of single-character edits necessary to
          transform one string into another.
          """
          ...






          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited 2 days ago

























          answered 2 days ago









          GraipherGraipher

          27k54497




          27k54497








          • 10




            $begingroup$
            Just to note the module is licensed under GPL 2.0 so watch out if you're using it for work.
            $endgroup$
            – lucasgcb
            2 days ago










          • $begingroup$
            Just to point out a small nitpick to other people who may stumble upon this answer, as per help center: "Every answer must make at least one insightful observation about the code in the question. Answers that merely provide an alternate solution with no explanation or justification do not constitute valid Code Review answers and may be deleted." While this answer does provide alternative and existing module suggestion, it also goes into some suggestions about improving code quality. So it's an example of a decent answer
            $endgroup$
            – Sergiy Kolodyazhnyy
            2 days ago










          • $begingroup$
            Thanks! I did not know of this module. Will check it out
            $endgroup$
            – Kyra_W
            yesterday






          • 1




            $begingroup$
            @SergiyKolodyazhnyy While I (obviously) agree, and that is one of the reasons I added that part, I would actually argue that "It is implemented in C, so is probably faster than anything you can come up with yourself" would get around the "no explanation or justification" clause
            $endgroup$
            – Graipher
            yesterday
















          • 10




            $begingroup$
            Just to note the module is licensed under GPL 2.0 so watch out if you're using it for work.
            $endgroup$
            – lucasgcb
            2 days ago










          • $begingroup$
            Just to point out a small nitpick to other people who may stumble upon this answer, as per help center: "Every answer must make at least one insightful observation about the code in the question. Answers that merely provide an alternate solution with no explanation or justification do not constitute valid Code Review answers and may be deleted." While this answer does provide alternative and existing module suggestion, it also goes into some suggestions about improving code quality. So it's an example of a decent answer
            $endgroup$
            – Sergiy Kolodyazhnyy
            2 days ago










          • $begingroup$
            Thanks! I did not know of this module. Will check it out
            $endgroup$
            – Kyra_W
            yesterday






          • 1




            $begingroup$
            @SergiyKolodyazhnyy While I (obviously) agree, and that is one of the reasons I added that part, I would actually argue that "It is implemented in C, so is probably faster than anything you can come up with yourself" would get around the "no explanation or justification" clause
            $endgroup$
            – Graipher
            yesterday










          10




          10




          $begingroup$
          Just to note the module is licensed under GPL 2.0 so watch out if you're using it for work.
          $endgroup$
          – lucasgcb
          2 days ago




          $begingroup$
          Just to note the module is licensed under GPL 2.0 so watch out if you're using it for work.
          $endgroup$
          – lucasgcb
          2 days ago












          $begingroup$
          Just to point out a small nitpick to other people who may stumble upon this answer, as per help center: "Every answer must make at least one insightful observation about the code in the question. Answers that merely provide an alternate solution with no explanation or justification do not constitute valid Code Review answers and may be deleted." While this answer does provide alternative and existing module suggestion, it also goes into some suggestions about improving code quality. So it's an example of a decent answer
          $endgroup$
          – Sergiy Kolodyazhnyy
          2 days ago




          $begingroup$
          Just to point out a small nitpick to other people who may stumble upon this answer, as per help center: "Every answer must make at least one insightful observation about the code in the question. Answers that merely provide an alternate solution with no explanation or justification do not constitute valid Code Review answers and may be deleted." While this answer does provide alternative and existing module suggestion, it also goes into some suggestions about improving code quality. So it's an example of a decent answer
          $endgroup$
          – Sergiy Kolodyazhnyy
          2 days ago












          $begingroup$
          Thanks! I did not know of this module. Will check it out
          $endgroup$
          – Kyra_W
          yesterday




          $begingroup$
          Thanks! I did not know of this module. Will check it out
          $endgroup$
          – Kyra_W
          yesterday




          1




          1




          $begingroup$
          @SergiyKolodyazhnyy While I (obviously) agree, and that is one of the reasons I added that part, I would actually argue that "It is implemented in C, so is probably faster than anything you can come up with yourself" would get around the "no explanation or justification" clause
          $endgroup$
          – Graipher
          yesterday






          $begingroup$
          @SergiyKolodyazhnyy While I (obviously) agree, and that is one of the reasons I added that part, I would actually argue that "It is implemented in C, so is probably faster than anything you can come up with yourself" would get around the "no explanation or justification" clause
          $endgroup$
          – Graipher
          yesterday















          9












          $begingroup$

          The code itself is rather clear. There are some smaller changes I would make



          tuple unpacking



          You can use tuple unpacking to do:



          for code, *_ in ndiff(str1, str2):


          instead of:



          for x in ndiff(str_1, str_2):
          code = x[0]


          dict results:



          Instead of a counter for the additions and removals, I would keep it in 1 dict: counter = ({"+": 0, "-": 0})



          def levenshtein_distance(str1, str2, ):
          counter = {"+": 0, "-": 0}
          distance = 0
          for edit_code, *_ in ndiff(str1, str2):
          if edit_code == " ":
          distance += max(counter.values())
          counter = {"+": 0, "-": 0}
          else:
          counter[edit_code] += 1
          distance += max(counter.values())
          return distance


          generators



          A smaller, less useful variation, is to let this method be a generator, and use the builtin sum to do the summary. this saves 1 variable inside the function:



          def levenshtein_distance_gen(str1, str2, ):
          counter = {"+": 0, "-": 0}
          for edit_code, *_ in ndiff(str1, str2):
          if edit_code == " ":
          yield max(counter.values())
          counter = {"+": 0, "-": 0}
          else:
          counter[edit_code] += 1
          yield max(counter.values())

          sum(levenshtein_distance_gen(str1, str2))




          timings



          The differences in timings between the original and both these variations are minimal, and within the variation of results. This is rather logical, since for simple strings (aaabbbc and abcabcabc) 90% of the time is spent in ndiff






          share|improve this answer









          $endgroup$













          • $begingroup$
            Awesome suggestions. I had not even considered the generator approach, but it looks very nice. Thanks
            $endgroup$
            – Kyra_W
            yesterday
















          9












          $begingroup$

          The code itself is rather clear. There are some smaller changes I would make



          tuple unpacking



          You can use tuple unpacking to do:



          for code, *_ in ndiff(str1, str2):


          instead of:



          for x in ndiff(str_1, str_2):
          code = x[0]


          dict results:



          Instead of a counter for the additions and removals, I would keep it in 1 dict: counter = ({"+": 0, "-": 0})



          def levenshtein_distance(str1, str2, ):
          counter = {"+": 0, "-": 0}
          distance = 0
          for edit_code, *_ in ndiff(str1, str2):
          if edit_code == " ":
          distance += max(counter.values())
          counter = {"+": 0, "-": 0}
          else:
          counter[edit_code] += 1
          distance += max(counter.values())
          return distance


          generators



          A smaller, less useful variation, is to let this method be a generator, and use the builtin sum to do the summary. this saves 1 variable inside the function:



          def levenshtein_distance_gen(str1, str2, ):
          counter = {"+": 0, "-": 0}
          for edit_code, *_ in ndiff(str1, str2):
          if edit_code == " ":
          yield max(counter.values())
          counter = {"+": 0, "-": 0}
          else:
          counter[edit_code] += 1
          yield max(counter.values())

          sum(levenshtein_distance_gen(str1, str2))




          timings



          The differences in timings between the original and both these variations are minimal, and within the variation of results. This is rather logical, since for simple strings (aaabbbc and abcabcabc) 90% of the time is spent in ndiff






          share|improve this answer









          $endgroup$













          • $begingroup$
            Awesome suggestions. I had not even considered the generator approach, but it looks very nice. Thanks
            $endgroup$
            – Kyra_W
            yesterday














          9












          9








          9





          $begingroup$

          The code itself is rather clear. There are some smaller changes I would make



          tuple unpacking



          You can use tuple unpacking to do:



          for code, *_ in ndiff(str1, str2):


          instead of:



          for x in ndiff(str_1, str_2):
          code = x[0]


          dict results:



          Instead of a counter for the additions and removals, I would keep it in 1 dict: counter = ({"+": 0, "-": 0})



          def levenshtein_distance(str1, str2, ):
          counter = {"+": 0, "-": 0}
          distance = 0
          for edit_code, *_ in ndiff(str1, str2):
          if edit_code == " ":
          distance += max(counter.values())
          counter = {"+": 0, "-": 0}
          else:
          counter[edit_code] += 1
          distance += max(counter.values())
          return distance


          generators



          A smaller, less useful variation, is to let this method be a generator, and use the builtin sum to do the summary. this saves 1 variable inside the function:



          def levenshtein_distance_gen(str1, str2, ):
          counter = {"+": 0, "-": 0}
          for edit_code, *_ in ndiff(str1, str2):
          if edit_code == " ":
          yield max(counter.values())
          counter = {"+": 0, "-": 0}
          else:
          counter[edit_code] += 1
          yield max(counter.values())

          sum(levenshtein_distance_gen(str1, str2))




          timings



          The differences in timings between the original and both these variations are minimal, and within the variation of results. This is rather logical, since for simple strings (aaabbbc and abcabcabc) 90% of the time is spent in ndiff






          share|improve this answer









          $endgroup$



          The code itself is rather clear. There are some smaller changes I would make



          tuple unpacking



          You can use tuple unpacking to do:



          for code, *_ in ndiff(str1, str2):


          instead of:



          for x in ndiff(str_1, str_2):
          code = x[0]


          dict results:



          Instead of a counter for the additions and removals, I would keep it in 1 dict: counter = ({"+": 0, "-": 0})



          def levenshtein_distance(str1, str2, ):
          counter = {"+": 0, "-": 0}
          distance = 0
          for edit_code, *_ in ndiff(str1, str2):
          if edit_code == " ":
          distance += max(counter.values())
          counter = {"+": 0, "-": 0}
          else:
          counter[edit_code] += 1
          distance += max(counter.values())
          return distance


          generators



          A smaller, less useful variation, is to let this method be a generator, and use the builtin sum to do the summary. this saves 1 variable inside the function:



          def levenshtein_distance_gen(str1, str2, ):
          counter = {"+": 0, "-": 0}
          for edit_code, *_ in ndiff(str1, str2):
          if edit_code == " ":
          yield max(counter.values())
          counter = {"+": 0, "-": 0}
          else:
          counter[edit_code] += 1
          yield max(counter.values())

          sum(levenshtein_distance_gen(str1, str2))




          timings



          The differences in timings between the original and both these variations are minimal, and within the variation of results. This is rather logical, since for simple strings (aaabbbc and abcabcabc) 90% of the time is spent in ndiff







          share|improve this answer












          share|improve this answer



          share|improve this answer










          answered 2 days ago









          Maarten FabréMaarten Fabré

          5,179517




          5,179517












          • $begingroup$
            Awesome suggestions. I had not even considered the generator approach, but it looks very nice. Thanks
            $endgroup$
            – Kyra_W
            yesterday


















          • $begingroup$
            Awesome suggestions. I had not even considered the generator approach, but it looks very nice. Thanks
            $endgroup$
            – Kyra_W
            yesterday
















          $begingroup$
          Awesome suggestions. I had not even considered the generator approach, but it looks very nice. Thanks
          $endgroup$
          – Kyra_W
          yesterday




          $begingroup$
          Awesome suggestions. I had not even considered the generator approach, but it looks very nice. Thanks
          $endgroup$
          – Kyra_W
          yesterday










          Kyra_W is a new contributor. Be nice, and check out our Code of Conduct.










          draft saved

          draft discarded


















          Kyra_W is a new contributor. Be nice, and check out our Code of Conduct.













          Kyra_W is a new contributor. Be nice, and check out our Code of Conduct.












          Kyra_W is a new contributor. Be nice, and check out our Code of Conduct.
















          Thanks for contributing an answer to Code Review Stack Exchange!


          • Please be sure to answer the question. Provide details and share your research!

          But avoid



          • Asking for help, clarification, or responding to other answers.

          • Making statements based on opinion; back them up with references or personal experience.


          Use MathJax to format equations. MathJax reference.


          To learn more, see our tips on writing great answers.




          draft saved


          draft discarded














          StackExchange.ready(
          function () {
          StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f217065%2fcalculate-levenshtein-distance-between-two-strings-in-python%23new-answer', 'question_page');
          }
          );

          Post as a guest















          Required, but never shown





















































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown

































          Required, but never shown














          Required, but never shown












          Required, but never shown







          Required, but never shown







          Popular posts from this blog

          GameSpot

          日野市

          Tu-95轟炸機