Ignorando mayúsculas y minúsculas, signos de puntuación y los espacios en blanco en las Cadenas de

Question

¿Cuál es la forma más eficiente de ignorando mayúsculas y minúsculas, signos de puntuación y los espacios en blanco en las cadenas?Estas cadenas deben ser divididos en palabras en lugar de los caracteres debe ignorar la mencionada detalles en las comparaciones, y las rodajas de estas palabras-las cadenas deberían ser tan eficiente como sea posible con la velocidad en mente.

Yo iba a caso de uso y los signos de puntuación insensible cadenas de caracteres para el código siguiente, pero después de ver cuánto tiempo le toma para evaluar class Slice: def __eq__(self, other): return self.root == other.root, He decidido trabajar con data = tuple(string.split()) en su lugar.Tener cadenas que son insensibles caso, la puntuación y el espacio y que funcionan a través de palabras en lugar de los caracteres era demasiado caro en el computacionalmente caro algoritmos ya expresado en el código de abajo.

class Slice:

    def __init__(self, data, offset, length):
        self.prefix = data[:offset]
        self.root = data[offset:offset+length]
        self.suffix = data[offset+length:]

    def __eq__(self, other):
        return self.root == other.root

    def __len__(self):
        return len(self.root)

################################################################################

class Match:

    def __init__(self, data, key, prefix_tree, suffix_tree):
        self.data = data
        self.key = key
        self.prefix_tree = prefix_tree
        self.suffix_tree = suffix_tree
        self.__value = len(key) + prefix_tree.value() + suffix_tree.value()

    def value(self):
        return self.__value

################################################################################

class Tree(tuple):

    def __new__(cls, nodes):
        tree = super().__new__(cls, nodes)
        tree.__value = max(map(Match.value, tree)) if tree else 0
        return tree

    def value(self):
        return self.__value

    def find(self, value):
        for index, match in enumerate(self):
            if match.value() == value:
                return index
        raise ValueError()

################################################################################

def search(data, key):
    length = 0
    nodes = []
    for d_block in shrink(data, len(key)):
        block_len = len(d_block)
        if length > block_len:
            return Tree(nodes)
        for k_block in slide(key, block_len):
            if d_block == k_block:
                length = block_len
                prefix_tree = search(d_block.prefix, k_block.prefix)
                suffix_tree = search(d_block.suffix, k_block.suffix)
                match = Match(d_block, k_block, prefix_tree, suffix_tree)
                nodes.append(match)
    return Tree(nodes)

def shrink(data, max_len):
    for length in range(min(len(data), max_len), 0, -1):
        for block in slide(data, length):
            yield block

def slide(data, length):
    for offset in range(len(data) - length + 1):
        yield Slice(data, offset, length)

################################################################################

def build_tree(nodes):
    match = nodes[nodes.find(nodes.value())]
    node = match.key
    if match.prefix_tree:
        node.prefix = build_tree(match.prefix_tree)
    if match.suffix_tree:
        node.suffix = build_tree(match.suffix_tree)
    return node

def flatten_tree(node):
    array = [0]
    _flatten(node, array)
    return tuple(array)

def _flatten(node, array):
    if isinstance(node.prefix, Slice):
        _flatten(node.prefix, array)
    else:
        array.append(node.prefix)
    array[0] += 1
    array.append((array[0], node.root))
    if isinstance(node.suffix, Slice):
        _flatten(node.suffix, array)
    else:
        array.append(node.suffix)

Answer 1

"¿Cuál es la mejor manera de solucionar este problema?"

La mejor, y la única, es definir lo que significa este objeto "y lo que significa la longitud de este objeto".

El objeto parece ser una lista de palabras. Nada mas. Ese parece ser el valor en _string.

No esta claro que _simple es, aparte de un subconjunto filtrado inaccesible de las palabras en _string.

Entonces, ¿cuál es la longitud? ¿La longitud de las palabras o la longitud de las palabras en el subconjunto filtrado?

Solo tú puedes definir lo que esta clase medio. los sentido Luego determinará cómo implementar __len__. Hasta que defina el significado, es imposible determinar cómo se debe implementar cualquier cosa.

Answer 2

Si desea iteración en una instancia de cadena para iterar en su self.__string, como tu __iter__ El método indica que la única opción sensata para la longitud es también devolver la longitud de __string -- podría ser realmente peculiar si len(x) y sum(1 for _ in x) dio como resultado diferentes valores.

Tengo que admitir que no entiendo el propósito de esta clase (y en particular por qué tomaste la terrible elección de tenerlo antiguo y por qué usas una forma tan contorsionada de construir __simple), pero la consistencia interna es importante de todos modos. Entonces, o cambie __iter__, o hacer __len__ lógicamente compatible con él.

Tu lógica de corte también me escapa totalmente: ¿por qué estás construyendo la porción? __simple de una manera que probablemente sea diferente de lo que obtendrías al reconstruirlo de la porción __string? Por ejemplo, si self.__string ¿Es '? ¡Boh!' y por lo tanto self.__simple es 'boh', ¿por qué desear self[1:-1] tener un __string de 'boh' pero con un __simple de 'O', tan incompatible, diferente e inconsistente del __simple ¿Obtendrías al recomputarlo de la porción ...?

Supongo que eso no está pertinente a esta Q sobre la longitud, pero tengo curiosidad por estas muchas opciones de diseño extremadamente peculiares que estás haciendo ...