prompt: You will be provided with a partial code base and an issue statement explaining a problem to resolve.
  <issue>
  Why Levenshtein Corrector make strange inserts inplace of punctuation marks?
  ```
  from deeppavlov.deep import find_config, deep_download
  from deeppavlov.core.commands.infer import build_model_from_config
  config = find_config('levenshtein_corrector_ru')
  deep_download(config)
  model = build_model_from_config(config)
  print(model(['Сегодня.']))
  print(model(['в 3 . Сегодня.']))
  ```
  Gives me
  > ['сегодня в']
  > ['в 3 и сегодня и']
  
  There are strange "." --> "в" and "." --> "и" inserts.
  
  </issue>
  <code>
  [start of deeppavlov/models/spelling_correction/levenshtein/searcher_component.py]
  1 # Copyright 2017 Neural Networks and Deep Learning lab, MIPT
  2 #
  3 # Licensed under the Apache License, Version 2.0 (the "License");
  4 # you may not use this file except in compliance with the License.
  5 # You may obtain a copy of the License at
  6 #
  7 #     http://www.apache.org/licenses/LICENSE-2.0
  8 #
  9 # Unless required by applicable law or agreed to in writing, software
  10 # distributed under the License is distributed on an "AS IS" BASIS,
  11 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12 # See the License for the specific language governing permissions and
  13 # limitations under the License.
  14 
  15 from math import log10
  16 from typing import Iterable, List, Tuple
  17 
  18 from deeppavlov.core.common.registry import register
  19 from deeppavlov.core.models.component import Component
  20 from deeppavlov.core.common.log import get_logger
  21 
  22 from .levenshtein_searcher import LevenshteinSearcher
  23 
  24 
  25 logger = get_logger(__name__)
  26 
  27 
  28 @register('spelling_levenshtein')
  29 class LevenshteinSearcherComponent(Component):
  30     """Component that finds replacement candidates for tokens at a set Damerau-Levenshtein distance
  31 
  32     Args:
  33         words: list of every correct word
  34         max_distance: maximum allowed Damerau-Levenshtein distance between source words and candidates
  35         error_probability: assigned probability for every edit
  36 
  37     Attributes:
  38         max_distance: maximum allowed Damerau-Levenshtein distance between source words and candidates
  39         error_probability: assigned logarithmic probability for every edit
  40         vocab_penalty: assigned logarithmic probability of an out of vocabulary token being the correct one without
  41          changes
  42     """
  43 
  44     def __init__(self, words: Iterable[str], max_distance: int=1, error_probability: float=1e-4, *args, **kwargs):
  45         words = list({word.strip().lower().replace('ё', 'е') for word in words})
  46         alphabet = sorted({letter for word in words for letter in word})
  47         self.max_distance = max_distance
  48         self.error_probability = log10(error_probability)
  49         self.vocab_penalty = self.error_probability * 2
  50         self.searcher = LevenshteinSearcher(alphabet, words, allow_spaces=True, euristics=2)
  51 
  52     def _infer_instance(self, tokens: Iterable[str]) -> List[List[Tuple[float, str]]]:
  53         candidates = []
  54         for word in tokens:
  55             c = {candidate: self.error_probability * distance
  56                  for candidate, distance in self.searcher.search(word, d=self.max_distance)}
  57             c[word] = c.get(word, self.vocab_penalty)
  58             candidates.append([(score, candidate) for candidate, score in c.items()])
  59         return candidates
  60 
  61     def __call__(self, batch: Iterable[Iterable[str]], *args, **kwargs) -> List[List[List[Tuple[float, str]]]]:
  62         """Propose candidates for tokens in sentences
  63 
  64         Args:
  65             batch: batch of tokenized sentences
  66 
  67         Returns:
  68             batch of lists of probabilities and candidates for every token
  69         """
  70         return [self._infer_instance(tokens) for tokens in batch]
  71
  [end of deeppavlov/models/spelling_correction/levenshtein/searcher_component.py]
  </code>
  
  I need you to solve this issue by generating a single patch file that I can apply directly to this repository using git apply. Please respond with a single patch file in the following format.
  <patch>
  diff --git a/file.py b/file.py
  --- a/file.py
  +++ b/file.py
  @@ -1,27 +1,35 @@
   def euclidean(a, b):
  -    while b:
  -        a, b = b, a % b
  -    return a
  +    if b == 0:
  +        return a
  +    return euclidean(b, a % b)
   
   
   def bresenham(x0, y0, x1, y1):
       points = []
       dx = abs(x1 - x0)
       dy = abs(y1 - y0)
  -    sx = 1 if x0 < x1 else -1
  -    sy = 1 if y0 < y1 else -1
  -    err = dx - dy
  +    x, y = x0, y0
  +    sx = -1 if x0 > x1 else 1
  +    sy = -1 if y0 > y1 else 1
   
  -    while True:
  -        points.append((x0, y0))
  -        if x0 == x1 and y0 == y1:
  -            break
  -        e2 = 2 * err
  -        if e2 > -dy:
  -            err -= dy
  -            x0 += sx
  -        if e2 < dx:
  -            err += dx
  -            y0 += sy
  +    if dx > dy:
  +        err = dx / 2.0
  +        while x != x1:
  +            points.append((x, y))
  +            err -= dy
  +            if err < 0:
  +                y += sy
  +                err += dx
  +            x += sx
  +    else:
  +        err = dy / 2.0
  +        while y != y1:
  +            points.append((x, y))
  +            err -= dx
  +            if err < 0:
  +                x += sx
  +                err += dy
  +            y += sy
  +
  +    points.append((x, y))
       return points
  
  </patch>
golden_diff: diff --git a/deeppavlov/models/spelling_correction/levenshtein/searcher_component.py b/deeppavlov/models/spelling_correction/levenshtein/searcher_component.py
  --- a/deeppavlov/models/spelling_correction/levenshtein/searcher_component.py
  +++ b/deeppavlov/models/spelling_correction/levenshtein/searcher_component.py
  @@ -11,7 +11,7 @@
   # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   # See the License for the specific language governing permissions and
   # limitations under the License.
  -
  +import string
   from math import log10
   from typing import Iterable, List, Tuple
   
  @@ -41,6 +41,8 @@
            changes
       """
   
  +    _punctuation = frozenset(string.punctuation)
  +
       def __init__(self, words: Iterable[str], max_distance: int=1, error_probability: float=1e-4, *args, **kwargs):
           words = list({word.strip().lower().replace('ё', 'е') for word in words})
           alphabet = sorted({letter for word in words for letter in word})
  @@ -52,10 +54,13 @@
       def _infer_instance(self, tokens: Iterable[str]) -> List[List[Tuple[float, str]]]:
           candidates = []
           for word in tokens:
  -            c = {candidate: self.error_probability * distance
  -                 for candidate, distance in self.searcher.search(word, d=self.max_distance)}
  -            c[word] = c.get(word, self.vocab_penalty)
  -            candidates.append([(score, candidate) for candidate, score in c.items()])
  +            if word in self._punctuation:
  +                candidates.append([(0, word)])
  +            else:
  +                c = {candidate: self.error_probability * distance
  +                     for candidate, distance in self.searcher.search(word, d=self.max_distance)}
  +                c[word] = c.get(word, self.vocab_penalty)
  +                candidates.append([(score, candidate) for candidate, score in c.items()])
           return candidates
   
       def __call__(self, batch: Iterable[Iterable[str]], *args, **kwargs) -> List[List[List[Tuple[float, str]]]]:
  
verification_info: {"golden_diff": "diff --git a/deeppavlov/models/spelling_correction/levenshtein/searcher_component.py b/deeppavlov/models/spelling_correction/levenshtein/searcher_component.py\n--- a/deeppavlov/models/spelling_correction/levenshtein/searcher_component.py\n+++ b/deeppavlov/models/spelling_correction/levenshtein/searcher_component.py\n@@ -11,7 +11,7 @@\n # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n # See the License for the specific language governing permissions and\n # limitations under the License.\n-\n+import string\n from math import log10\n from typing import Iterable, List, Tuple\n \n@@ -41,6 +41,8 @@\n          changes\n     \"\"\"\n \n+    _punctuation = frozenset(string.punctuation)\n+\n     def __init__(self, words: Iterable[str], max_distance: int=1, error_probability: float=1e-4, *args, **kwargs):\n         words = list({word.strip().lower().replace('\u0451', '\u0435') for word in words})\n         alphabet = sorted({letter for word in words for letter in word})\n@@ -52,10 +54,13 @@\n     def _infer_instance(self, tokens: Iterable[str]) -> List[List[Tuple[float, str]]]:\n         candidates = []\n         for word in tokens:\n-            c = {candidate: self.error_probability * distance\n-                 for candidate, distance in self.searcher.search(word, d=self.max_distance)}\n-            c[word] = c.get(word, self.vocab_penalty)\n-            candidates.append([(score, candidate) for candidate, score in c.items()])\n+            if word in self._punctuation:\n+                candidates.append([(0, word)])\n+            else:\n+                c = {candidate: self.error_probability * distance\n+                     for candidate, distance in self.searcher.search(word, d=self.max_distance)}\n+                c[word] = c.get(word, self.vocab_penalty)\n+                candidates.append([(score, candidate) for candidate, score in c.items()])\n         return candidates\n \n     def __call__(self, batch: Iterable[Iterable[str]], *args, **kwargs) -> List[List[List[Tuple[float, str]]]]:\n", "issue": "Why Levenshtein Corrector make strange inserts inplace of punctuation marks?\n```\r\nfrom deeppavlov.deep import find_config, deep_download\r\nfrom deeppavlov.core.commands.infer import build_model_from_config\r\nconfig = find_config('levenshtein_corrector_ru')\r\ndeep_download(config)\r\nmodel = build_model_from_config(config)\r\nprint(model(['\u0421\u0435\u0433\u043e\u0434\u043d\u044f.']))\r\nprint(model(['\u0432 3 . \u0421\u0435\u0433\u043e\u0434\u043d\u044f.']))\r\n```\r\nGives me\r\n> ['\u0441\u0435\u0433\u043e\u0434\u043d\u044f \u0432']\r\n> ['\u0432 3 \u0438 \u0441\u0435\u0433\u043e\u0434\u043d\u044f \u0438']\r\n\r\nThere are strange \".\" --> \"\u0432\" and \".\" --> \"\u0438\" inserts.\n", "before_files": [{"content": "# Copyright 2017 Neural Networks and Deep Learning lab, MIPT\n#\n# Licensed under the Apache License, Version 2.0 (the \"License\");\n# you may not use this file except in compliance with the License.\n# You may obtain a copy of the License at\n#\n#     http://www.apache.org/licenses/LICENSE-2.0\n#\n# Unless required by applicable law or agreed to in writing, software\n# distributed under the License is distributed on an \"AS IS\" BASIS,\n# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n# See the License for the specific language governing permissions and\n# limitations under the License.\n\nfrom math import log10\nfrom typing import Iterable, List, Tuple\n\nfrom deeppavlov.core.common.registry import register\nfrom deeppavlov.core.models.component import Component\nfrom deeppavlov.core.common.log import get_logger\n\nfrom .levenshtein_searcher import LevenshteinSearcher\n\n\nlogger = get_logger(__name__)\n\n\n@register('spelling_levenshtein')\nclass LevenshteinSearcherComponent(Component):\n    \"\"\"Component that finds replacement candidates for tokens at a set Damerau-Levenshtein distance\n\n    Args:\n        words: list of every correct word\n        max_distance: maximum allowed Damerau-Levenshtein distance between source words and candidates\n        error_probability: assigned probability for every edit\n\n    Attributes:\n        max_distance: maximum allowed Damerau-Levenshtein distance between source words and candidates\n        error_probability: assigned logarithmic probability for every edit\n        vocab_penalty: assigned logarithmic probability of an out of vocabulary token being the correct one without\n         changes\n    \"\"\"\n\n    def __init__(self, words: Iterable[str], max_distance: int=1, error_probability: float=1e-4, *args, **kwargs):\n        words = list({word.strip().lower().replace('\u0451', '\u0435') for word in words})\n        alphabet = sorted({letter for word in words for letter in word})\n        self.max_distance = max_distance\n        self.error_probability = log10(error_probability)\n        self.vocab_penalty = self.error_probability * 2\n        self.searcher = LevenshteinSearcher(alphabet, words, allow_spaces=True, euristics=2)\n\n    def _infer_instance(self, tokens: Iterable[str]) -> List[List[Tuple[float, str]]]:\n        candidates = []\n        for word in tokens:\n            c = {candidate: self.error_probability * distance\n                 for candidate, distance in self.searcher.search(word, d=self.max_distance)}\n            c[word] = c.get(word, self.vocab_penalty)\n            candidates.append([(score, candidate) for candidate, score in c.items()])\n        return candidates\n\n    def __call__(self, batch: Iterable[Iterable[str]], *args, **kwargs) -> List[List[List[Tuple[float, str]]]]:\n        \"\"\"Propose candidates for tokens in sentences\n\n        Args:\n            batch: batch of tokenized sentences\n\n        Returns:\n            batch of lists of probabilities and candidates for every token\n        \"\"\"\n        return [self._infer_instance(tokens) for tokens in batch]\n", "path": "deeppavlov/models/spelling_correction/levenshtein/searcher_component.py"}]}