<commit_before># Copyright (C) 2016 Yggdroot
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#      http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# 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.

#!/usr/bin/env python
# -*- coding: utf-8 -*-


class FuzzyMatch(object):
    def __init__(self, pattern):
        self._pattern = pattern
        self._pattern_mask = {}
        self._is_pattern_lower = (pattern + 'a').islower()
        for i, c in enumerate(pattern):
            if c in self._pattern_mask:
                self._pattern_mask[c] ^= (1 << i)
            else:
                self._pattern_mask[c] = ~0 ^ (1 << i)

    @staticmethod
    def evaluate(text, pattern, text_mask, j, pattern_mask, k, val):
        x = text_mask[pattern[0]] >> j
        # e.g., text = 'a~bc~d~~ab~~d~', pattern = 'abcd'
        if x == 0:
            return (0, 0, 0)
        # e.g., text = '~ab~~_abd~b~d', pattern = 'abbd'
        if k in val and val[k][2] > j + 1:
            return val[k]
        max_prefix_score = max_score = beg = end = 0
        i = ((x & -x) - 1).bit_length()
        if i == 0 or text[i-1] in '_- ':
            special = 2
        elif text[i].isupper():
            special = 2 if not text[i-1].isupper() else 0
        elif text[i-1] == '.':
            special = 1.9
        elif text[i-1] in '/\\':
            special = 2
        # elif not text[i-1].isalnum() :    # ;,"'...
        #     special = 2
        else:
            special = 0
        d = -2      # -0b10 or ~1
        i += 1
        text_len = len(text)
        pattern_len = len(pattern)
        while i < text_len:
            last = d
            c = text[i]
            if c in pattern_mask:
                d = d << 1 | pattern_mask[c] >> k
            elif (text[i-1].isupper() and c.lower() in pattern_mask and
                    (i+1 == text_len or not text[i+1].islower())):
                d = d << 1 | pattern_mask[c.lower()] >> k
            else:
                d = ~0
            if d > last:
                n = (~last).bit_length()
                # e.g., text = '~~abcd~~~~', pattern = 'abcd'
                if n == pattern_len:
                    score = n*n + special
                    if special == 2:
                        val[k] = (score, i-n, j+i)
                        return val[k]
                    else:
                        end_pos = j + i
                else:
                    prefix_score = n*n + special
                    if prefix_score > max_prefix_score:
                        max_prefix_score = prefix_score
                        res = FuzzyMatch.evaluate(text[i:],
                                                  pattern[n:],
                                                  text_mask,
                                                  j+i,
                                                  pattern_mask,
                                                  k+n,
                                                  val)
                        score = prefix_score + res[0] if res[0] else 0
                        end_pos = res[2]
                    else:
                        score = 0
                if score > max_score:
                    max_score = score
                    beg = i - n
                    end = end_pos
            # e.g., text = 'a~c~~~~ab~c', pattern = 'abc',
            # to find the index of the second 'a'
            if d == ~0:
                y = x >> i
                if y == 0:
                    break
                else:
                    i += ((y & -y) - 1).bit_length()
                    if text[i].isupper():
                        special = 2 if not text[i-1].isupper() else 0
                    elif text[i-1] in '_- ':
                        special = 2
                    elif text[i-1] == '.':
                        special = 1.9
                    elif text[i-1] in '/\\':
                        special = 2
                    # elif not text[i-1].isalnum() :    # ;,"'...
                    #     special = 2
                    else:
                        special = 0
                    d = -2      # -0b10 or ~1
                    i += 1
            else:
                i += 1
        else:
            # e.g., text = '~~~~abcd', pattern = 'abcd'
            if ~d >> (pattern_len - 1):
                score = pattern_len*pattern_len + special
                if score > max_score:
                    max_score = score
                    beg = i - pattern_len
                    end = j + i
        val[k] = (max_score, beg, end)
        return val[k]

    @staticmethod
    def evaluateOneChar(text, pattern):
        if pattern.isupper():
            beg = text.find(pattern)
            return 0 if beg == -1 else 1.0/(beg + 1) + 1.0/len(text)
        text_lower = text.lower()
        beg = text_lower.find(pattern)
        if beg == -1:
            return 0
        special = 0
        if text[beg].isupper() or beg == 0 or text[beg-1] in '_.- /\\':
            special = 2
        else:
            second = text_lower.find(pattern, beg + 1)
            if second != -1 and (text[second].isupper() or
                                 text[second-1] in '_.- /\\'):
                special = 2
                beg = second
        return special + 1.0/(beg + 1) + 1.0/len(text)

    @staticmethod
    def evaluateTwoChar(text, pattern, is_pattern_lower):
        if is_pattern_lower:
            text_lower = text.lower()
            beg = text_lower.find(pattern)
            special = 0
            if beg != -1:
                if text[beg].isupper() or beg == 0 or text[beg-1] in '_.- /\\':
                    special = 2
                else:
                    second_beg = text_lower.find(pattern, beg + 1)
                    if second_beg != -1 and (text[second_beg].isupper() or
                                             text[second_beg-1] in '_.- /\\'):
                        special = 2
                        beg = second_beg
                return 4 + special + 1.0/(beg + 1) + 1.0/len(text)
            else:
                beg = text_lower.find(pattern[0])
                if beg == -1:
                    return 0
                if text[beg].isupper() or beg == 0 or text[beg-1] in '_.- /\\':
                    special = 2
                end = text_lower.find(pattern[1], beg + 1)
                if end == -1:
                    return 0
                if text[end].isupper() or end == 0 or text[end-1] in '_.- /\\':
                    special += 2
                else:
                    second_end = text_lower.find(pattern[1], end + 1)
                    if second_end != -1 and (text[second_end].isupper() or
                                             text[second_end-1] in '_.- /\\'):
                        if special != 2:
                            second_beg = text_lower.find(pattern[0], beg + 1, second_end)
                            if second_beg != -1 and (text[second_beg].isupper() or
                                                     text[second_beg-1] in '_.- /\\'):
                                special = 2
                                beg = second_beg
                        special += 2
                        end = second_end
                return 2 + special + 1.0/(beg + end) + 1.0/len(text)
        elif pattern[0].isupper():
            beg = text.find(pattern[0])
            if beg == -1:
                return 0
            if pattern[1].isupper(): # e.g. pattern is 'AB'
                end = text.find(pattern[1], beg + 1)
                return 0 if end == -1 else 1.0/(beg + end) + 1.0/len(text)
            else:   # e.g. pattern is 'Ab'
                text_lower = text.lower()
                end = text_lower.find(pattern[1], beg + 1)
                if end == -1:
                    return 0
                elif end == beg + 1:
                    return 4 + 1.0/(beg + end) + 1.0/len(text)
                special = 0
                if text[end].isupper() or text[end-1] in '_.- /\\':
                    special = 2
                else:
                    second_end = text_lower.find(pattern[1], end + 1)
                    if second_end != -1 and (text[second_end].isupper() or
                                             text[second_end-1] in '_.- /\\'):
                        special = 2
                return 2 + special + 1.0/(beg + end) + 1.0/len(text)
        else: # e.g. pattern is 'aB'
            text_lower = text.lower()
            beg = text_lower.find(pattern[0])
            if beg == -1:
                return 0
            end = text.find(pattern[1], beg + 1)
            if end == -1:
                return 0
            special = 0
            if text[beg].isupper() or beg == 0 or text[beg-1] in '_.- /\\':
                special = 2
            else:
                second_beg = text_lower.find(pattern[0], beg + 1, end)
                if second_beg != -1 and (text[second_beg].isupper() or
                                         text[second_beg-1] in '_.- /\\'):
                    special = 2
                    beg = second_beg
            return 2 + special + 1.0/(beg + end) + 1.0/len(text)

    def getWeight(self, text):
        pattern_len = len(self._pattern)
        if pattern_len == 1:
            return FuzzyMatch.evaluateOneChar(text, self._pattern)
        elif pattern_len == 2:
            return FuzzyMatch.evaluateTwoChar(text, self._pattern,
                                              self._is_pattern_lower)
        j = 0
        first_char = self._pattern[0]
        last_char = self._pattern[-1]
        if self._is_pattern_lower:
            text_lower = text.lower()
            first_char_pos = text_lower.find(first_char)
            if first_char_pos == -1:
                return 0
            last_char_pos = text_lower.rfind(last_char, first_char_pos)
            if last_char_pos == -1:
                return 0
            text_mask = {}
            for c in self._pattern_mask:
                text_mask[c] = 0
            for i, c in enumerate(text_lower[first_char_pos : last_char_pos+1],
                                  first_char_pos):
                if c in text_mask:
                    text_mask[c] |= (1 << i)
                    if j < pattern_len and c == self._pattern[j]:
                        j += 1
        else:
            if first_char.isupper():
                first_char_pos = text.find(first_char)
            else:
                first_char_pos = -1
                for i, c in enumerate(text):
                    if first_char == c.lower():
                        first_char_pos = i
                        break
            if first_char_pos == -1:
                return 0
            if last_char.isupper():
                last_char_pos = text.rfind(last_char, first_char_pos)
            else:
                last_char_pos = -1
                for i, c in enumerate(reversed(text[first_char_pos:])):
                    if last_char == c.lower():
                        last_char_pos = len(text) - 1 - i
                        break
            if last_char_pos == -1:
                return 0
            text_mask = {}
            for c in self._pattern_mask:
                text_mask[c] = 0
            for i, c in enumerate(text[first_char_pos : last_char_pos+1],
                                  first_char_pos):
                if c.isupper():
                    if c in text_mask:
                        text_mask[c] |= (1 << i)
                    if c.lower() in text_mask:
                        text_mask[c.lower()] |= (1 << i)
                    if j < pattern_len and (c == self._pattern[j] or
                            c.lower() == self._pattern[j]):
                        j += 1
                else:
                    if c in text_mask:
                        text_mask[c] |= (1 << i)
                        if j < pattern_len and c == self._pattern[j]:
                            j += 1
        if j < pattern_len:
            return 0
        val = {}
        (score, beg, end) = FuzzyMatch.evaluate(text,
                                                self._pattern,
                                                text_mask,
                                                0,
                                                self._pattern_mask,
                                                0,
                                                val)
        return score + (1 >> beg) + 0.4/(end - beg) + 1.0/(beg + end) + 1.0/len(text)

<commit_msg>fix an issue e.g., text = 'kpi_ooaaaaa', pattern = 'kpio' e.g., text = 'aaaaaaaaaaaaaaaa', pattern = 'aaa'<commit_after># Copyright (C) 2016 Yggdroot
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#      http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# 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.

#!/usr/bin/env python
# -*- coding: utf-8 -*-


class FuzzyMatch(object):
    def __init__(self, pattern):
        self._pattern = pattern
        self._pattern_mask = {}
        self._is_pattern_lower = (pattern + 'a').islower()
        for i, c in enumerate(pattern):
            if c in self._pattern_mask:
                self._pattern_mask[c] ^= (1 << i)
            else:
                self._pattern_mask[c] = ~0 ^ (1 << i)

    @staticmethod
    def evaluate(text, pattern, text_mask, j, pattern_mask, k, val):
        x = text_mask[pattern[0]] >> j
        # e.g., text = 'a~bc~d~~ab~~d~', pattern = 'abcd'
        if x == 0:
            return (0, 0, 0)
        # e.g., text = '~ab~~_abd~b~d', pattern = 'abbd'
        if k in val and val[k][2] > j + 1:
            return val[k]
        max_prefix_score = max_score = beg = end = 0
        i = ((x & -x) - 1).bit_length()
        if i == 0 or text[i-1] in '_- ':
            special = 2
        elif text[i].isupper():
            special = 2 if not text[i-1].isupper() else 0
        elif text[i-1] == '.':
            special = 1.9
        elif text[i-1] in '/\\':
            special = 2
        # elif not text[i-1].isalnum() :    # ;,"'...
        #     special = 2
        else:
            special = 0
        d = -2      # -0b10 or ~1
        i += 1
        text_len = len(text)
        pattern_len = len(pattern)
        while i < text_len:
            last = d
            c = text[i]
            if c in pattern_mask:
                d = d << 1 | pattern_mask[c] >> k
            elif (text[i-1].isupper() and c.lower() in pattern_mask and
                    (i+1 == text_len or not text[i+1].islower())):
                d = d << 1 | pattern_mask[c.lower()] >> k
            else:
                d = ~0
            if d >= last:
                n = (~last).bit_length()
                # e.g., text = '~~abcd~~~~', pattern = 'abcd'
                if n == pattern_len:
                    score = n*n + special
                    if special == 2:
                        val[k] = (score, i-n, j+i)
                        return val[k]
                    else:
                        end_pos = j + i
                else:
                    prefix_score = n*n + special
                    if prefix_score > max_prefix_score:
                        max_prefix_score = prefix_score
                        res = FuzzyMatch.evaluate(text[i:],
                                                  pattern[n:],
                                                  text_mask,
                                                  j+i,
                                                  pattern_mask,
                                                  k+n,
                                                  val)
                        score = prefix_score + res[0] if res[0] else 0
                        end_pos = res[2]
                    else:
                        score = 0
                if score > max_score:
                    max_score = score
                    beg = i - n
                    end = end_pos
            # e.g., text = 'a~c~~~~ab~c', pattern = 'abc',
            # to find the index of the second 'a'
            if d == ~0:
                y = x >> i
                if y == 0:
                    break
                else:
                    i += ((y & -y) - 1).bit_length()
                    if text[i].isupper():
                        special = 2 if not text[i-1].isupper() else 0
                    elif text[i-1] in '_- ':
                        special = 2
                    elif text[i-1] == '.':
                        special = 1.9
                    elif text[i-1] in '/\\':
                        special = 2
                    # elif not text[i-1].isalnum() :    # ;,"'...
                    #     special = 2
                    else:
                        special = 0
                    d = -2      # -0b10 or ~1
                    i += 1
            else:
                i += 1
        else:
            # e.g., text = '~~~~abcd', pattern = 'abcd'
            if ~d >> (pattern_len - 1):
                score = pattern_len*pattern_len + special
                if score > max_score:
                    max_score = score
                    beg = i - pattern_len
                    end = j + i
        val[k] = (max_score, beg, end)
        return val[k]

    @staticmethod
    def evaluateOneChar(text, pattern):
        if pattern.isupper():
            beg = text.find(pattern)
            return 0 if beg == -1 else 1.0/(beg + 1) + 1.0/len(text)
        text_lower = text.lower()
        beg = text_lower.find(pattern)
        if beg == -1:
            return 0
        special = 0
        if text[beg].isupper() or beg == 0 or text[beg-1] in '_.- /\\':
            special = 2
        else:
            second = text_lower.find(pattern, beg + 1)
            if second != -1 and (text[second].isupper() or
                                 text[second-1] in '_.- /\\'):
                special = 2
                beg = second
        return special + 1.0/(beg + 1) + 1.0/len(text)

    @staticmethod
    def evaluateTwoChar(text, pattern, is_pattern_lower):
        if is_pattern_lower:
            text_lower = text.lower()
            beg = text_lower.find(pattern)
            special = 0
            if beg != -1:
                if text[beg].isupper() or beg == 0 or text[beg-1] in '_.- /\\':
                    special = 2
                else:
                    second_beg = text_lower.find(pattern, beg + 1)
                    if second_beg != -1 and (text[second_beg].isupper() or
                                             text[second_beg-1] in '_.- /\\'):
                        special = 2
                        beg = second_beg
                return 4 + special + 1.0/(beg + 1) + 1.0/len(text)
            else:
                beg = text_lower.find(pattern[0])
                if beg == -1:
                    return 0
                if text[beg].isupper() or beg == 0 or text[beg-1] in '_.- /\\':
                    special = 2
                end = text_lower.find(pattern[1], beg + 1)
                if end == -1:
                    return 0
                if text[end].isupper() or end == 0 or text[end-1] in '_.- /\\':
                    special += 2
                else:
                    second_end = text_lower.find(pattern[1], end + 1)
                    if second_end != -1 and (text[second_end].isupper() or
                                             text[second_end-1] in '_.- /\\'):
                        if special != 2:
                            second_beg = text_lower.find(pattern[0], beg + 1, second_end)
                            if second_beg != -1 and (text[second_beg].isupper() or
                                                     text[second_beg-1] in '_.- /\\'):
                                special = 2
                                beg = second_beg
                        special += 2
                        end = second_end
                return 2 + special + 1.0/(beg + end) + 1.0/len(text)
        elif pattern[0].isupper():
            beg = text.find(pattern[0])
            if beg == -1:
                return 0
            if pattern[1].isupper(): # e.g. pattern is 'AB'
                end = text.find(pattern[1], beg + 1)
                return 0 if end == -1 else 1.0/(beg + end) + 1.0/len(text)
            else:   # e.g. pattern is 'Ab'
                text_lower = text.lower()
                end = text_lower.find(pattern[1], beg + 1)
                if end == -1:
                    return 0
                elif end == beg + 1:
                    return 4 + 1.0/(beg + end) + 1.0/len(text)
                special = 0
                if text[end].isupper() or text[end-1] in '_.- /\\':
                    special = 2
                else:
                    second_end = text_lower.find(pattern[1], end + 1)
                    if second_end != -1 and (text[second_end].isupper() or
                                             text[second_end-1] in '_.- /\\'):
                        special = 2
                return 2 + special + 1.0/(beg + end) + 1.0/len(text)
        else: # e.g. pattern is 'aB'
            text_lower = text.lower()
            beg = text_lower.find(pattern[0])
            if beg == -1:
                return 0
            end = text.find(pattern[1], beg + 1)
            if end == -1:
                return 0
            special = 0
            if text[beg].isupper() or beg == 0 or text[beg-1] in '_.- /\\':
                special = 2
            else:
                second_beg = text_lower.find(pattern[0], beg + 1, end)
                if second_beg != -1 and (text[second_beg].isupper() or
                                         text[second_beg-1] in '_.- /\\'):
                    special = 2
                    beg = second_beg
            return 2 + special + 1.0/(beg + end) + 1.0/len(text)

    def getWeight(self, text):
        pattern_len = len(self._pattern)
        if pattern_len == 1:
            return FuzzyMatch.evaluateOneChar(text, self._pattern)
        elif pattern_len == 2:
            return FuzzyMatch.evaluateTwoChar(text, self._pattern,
                                              self._is_pattern_lower)
        j = 0
        first_char = self._pattern[0]
        last_char = self._pattern[-1]
        if self._is_pattern_lower:
            text_lower = text.lower()
            first_char_pos = text_lower.find(first_char)
            if first_char_pos == -1:
                return 0
            last_char_pos = text_lower.rfind(last_char, first_char_pos)
            if last_char_pos == -1:
                return 0
            text_mask = {}
            for c in self._pattern_mask:
                text_mask[c] = 0
            for i, c in enumerate(text_lower[first_char_pos : last_char_pos+1],
                                  first_char_pos):
                if c in text_mask:
                    text_mask[c] |= (1 << i)
                    if j < pattern_len and c == self._pattern[j]:
                        j += 1
        else:
            if first_char.isupper():
                first_char_pos = text.find(first_char)
            else:
                first_char_pos = -1
                for i, c in enumerate(text):
                    if first_char == c.lower():
                        first_char_pos = i
                        break
            if first_char_pos == -1:
                return 0
            if last_char.isupper():
                last_char_pos = text.rfind(last_char, first_char_pos)
            else:
                last_char_pos = -1
                for i, c in enumerate(reversed(text[first_char_pos:])):
                    if last_char == c.lower():
                        last_char_pos = len(text) - 1 - i
                        break
            if last_char_pos == -1:
                return 0
            text_mask = {}
            for c in self._pattern_mask:
                text_mask[c] = 0
            for i, c in enumerate(text[first_char_pos : last_char_pos+1],
                                  first_char_pos):
                if c.isupper():
                    if c in text_mask:
                        text_mask[c] |= (1 << i)
                    if c.lower() in text_mask:
                        text_mask[c.lower()] |= (1 << i)
                    if j < pattern_len and (c == self._pattern[j] or
                            c.lower() == self._pattern[j]):
                        j += 1
                else:
                    if c in text_mask:
                        text_mask[c] |= (1 << i)
                        if j < pattern_len and c == self._pattern[j]:
                            j += 1
        if j < pattern_len:
            return 0
        val = {}
        (score, beg, end) = FuzzyMatch.evaluate(text,
                                                self._pattern,
                                                text_mask,
                                                0,
                                                self._pattern_mask,
                                                0,
                                                val)
        return score + (1 >> beg) + 0.4/(end - beg) + 1.0/(beg + end) + 1.0/len(text)


{'fraction_non_alphanumeric': 0.10964337980435955, 'fraction_numerical': 0.018254640683971347, 'mean_word_length': 0.9694349639742131, 'pattern_counts': {'":': 0, '<': 45, '<?xml version=': 0, '>': 37, 'https://': 0, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 1, 'word_list_counts': {'cursed_substrings.json': 80, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2204866', 'n_tokens_mistral': 7505, 'n_tokens_neox': 6864, 'n_words': 1904}