0

忽略字符串中的大小写、标点符号和空格的最有效方法是什么？这些字符串应该被分成单词而不是字符应该忽略前面提到的比较细节，并且这些单词字符串的切片应该尽可能高效并考虑到速度。

我打算在下面的代码中使用不区分大小写和标点符号的字符串，但是在看到评估需要多长时间之后class Slice: def __eq__(self, other): return self.root == other.root，我决定data = tuple(string.split())改用它。对于已经在下面的代码中表达的计算量大的算法来说，让字符串对大小写、标点符号和间距不敏感，并且对单词而不是字符起作用，这太昂贵了。

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)
4

2 回答 2

2

如果您希望对 String 实例进行迭代以对其进行迭代self.__string，如您的__iter__方法所示，长度的唯一明智选择也是返回的长度- 如果并导致不同的值__string，这将是非常特殊的。len(x)sum(1 for _ in x)

我不得不承认我不明白这个类的目的（特别是为什么你做出了旧式的可怕选择，以及为什么你使用这种扭曲的方式来构建__simple），但无论如何内部一致性很重要。所以，要么改变__iter__，要么在__len__逻辑上与之兼容。

你的切片逻辑也完全让我无法理解——为什么你构建切片的__simple方式可能与你从切片重建它得到的不同__string？例如，如果self.__string是 '?Boh!' 因此self.__simple是'boh'，为什么你想要 self[1:-1]一个__string'Boh'但有一个'o'，与你通过从切片重新计算得到的__simple不兼容、不同和不一致......？__simple

我想这与这个关于长度的问题无关，但我只是对你正在做出的许多极其奇特的设计选择感到好奇......

于 2010-01-30T19:51:47.957 回答
2

“解决这个问题的最佳方法是什么？”

最好的——也是唯一的——方法是定义这个对象“意味着”什么以及这个对象的长度“意味着”什么。

该对象似乎是一个单词列表。而已。这似乎是_string.

目前尚不清楚是什么_simple，除了_string.

那么长度是多少呢？过滤后的子集中词的长度还是词的长度？

只有您可以定义此类的含义。其含义将决定如何实现__len__。在定义含义之前，不可能确定应该如何实现任何东西。

于 2010-01-30T20:32:01.307 回答