Python - удалить все слова, которые содержат другие слова в списке

Question

У меня есть список, заполненный словами из словаря.Я хочу найти способ удалить все слова, только рассматривая корневые слова, которые образуются в начале целевого слова.

Например, слово «родео» будет удалено из списка, поскольку оно содержит действительное на английском языке слово «роде».«Пишущая машинка» будет удалена, поскольку она содержит действительное на английском языке слово «тип».Тем не менее, слово «сникер» остается в силе, даже если оно содержит слово «ник», потому что «ник» находится в середине, а не в начале слова.

Я думал примерно так:

 for line in wordlist:
        if line.find(...) --

но я хочу, чтобы этот оператор «if» проходил через каждое отдельное слово в списке, проверяя, найдено ли его, и, если это так, удаляет себя из списка, чтобы остались только корневые слова.Нужно ли создавать копию списка слов для прохождения?

Answer 1

Итак, у вас есть два списка: список слов, которые вы хотите проверить и, возможно, удалить, и список допустимых слов. Если хотите, вы можете использовать один и тот же список для обеих целей, но я предполагаю, что у вас есть два списка.

Для скорости вы должны превратить ваш список допустимых слов в набор. Затем вы можете очень быстро проверить, есть ли какое-то конкретное слово в этом наборе. Затем возьмите каждое слово и проверьте, существуют ли все его префиксы в списке допустимых слов или нет. Поскольку «a» и «I» являются допустимыми словами на английском языке, вы удалите все допустимые слова, начинающиеся с «a», или у вас будет правило, устанавливающее минимальную длину префикса?

Я использую файл / usr / share / dict / words из моей установки Ubuntu. В этом файле много разных странных вещей; например, он, кажется, содержит каждую букву как слово. Таким образом, "k" там, "q", "z" и т. Д. Насколько мне известно, ни одно из этих слов не является словом, но они, вероятно, присутствуют там по какой-то технической причине. Во всяком случае, я решил просто исключить что-нибудь короче, чем три буквы из моего списка допустимых слов.

Вот что я придумал:

# build valid list from /usr/dict/share/words
wfile = "/usr/dict/share/words"
valid = set(line.strip() for line in open(wfile) if len(line) >= 3)

lst = ["ark", "booze", "kite", "live", "rodeo"]

def subwords(word):
    for i in range(len(word) - 1, 0, -1):
        w = word[:i]
        yield w

newlst = []
for word in lst:
    # uncomment these for debugging to make sure it works
    # print "subwords", [w for w in subwords(word)]
    # print "valid subwords", [w for w in subwords(word) if w in valid]
    if not any(w in valid for w in subwords(word)):
        newlst.append(word)

print(newlst)

Если вы фанат однострочников, вы можете покончить с списком «for» и использовать понимание списка:

newlst = [word for word in lst if not any(w in valid for w in subwords(word))]

Я думаю, что это более кратко, чем должно быть, и мне нравится возможность вставлять операторы print для отладки.

Хм, если подумать, это не слишком кратко, если вы просто добавите еще одну функцию:

def keep(word):
    return not any(w in valid for w in subwords(word))

newlst = [word for word in lst if keep(word)]

Python может быть легко читаемым и понятным, если вы создадите такие функции и дадите им хорошие имена.

Answer 2

Я предполагаю, что у вас есть только один список, из которого вы хотите удалить все элементы, имеющие префиксы в этом же списке.

#Important assumption here... wordlist is sorted

base=wordlist[0]                      #consider the first word in the list
for word in wordlist:                 #loop through the entire list checking if
    if not word.startswith(base):     # the word we're considering starts with the base
        print base                    #If not... we have a new base, print the current
        base=word                     #  one and move to this new one
    #else word starts with base
        #don't output word, and go on to the next item in the list
print base                            #finish by printing the last base

РЕДАКТИРОВАТЬ: добавлены некоторые комментарии, чтобы сделать логику более очевидной

Answer 3

Я написал ответ, который предполагает два списка: список, который нужно удалить, и список допустимых слов.В дискуссии вокруг моего ответа я прокомментировал, что, может быть, было бы неплохо решение с помощью trie.

Какого черта, я пошел дальше и написал это.

Вы можете прочитать о trie здесь:

http://en.wikipedia.org/wiki/Trie

Для своего решения на Python я в основном использовал словари.Ключ - это последовательность символов, и каждый символ вступает в диктовку с другим экземпляром Trie в качестве данных.Второй словарь хранит «терминальные» символы, которые отмечают конец «слова» в Trie.В этом примере «слова» на самом деле являются словами, но в принципе слова могут быть любой последовательностью хэшируемых объектов Python.

Пример Wikipedia показывает три, где ключи являются буквами, но может быть больше чемодна буква;они могут быть последовательностью из нескольких букв.Для простоты мой код использует только один символ за раз в качестве ключа.

Если вы добавите и слово "cat", и слово "catch" в дерево, тогда будут узлы для 'c',' a 'и' t '(а также второе' c 'в слове "catch").На уровне узла для «a» словарь «терминалов» будет содержать «t» (таким образом, завершая кодирование для «cat»), а также на более глубоком уровне узла второго «c» словарь терминаловбудет иметь 'H' в (завершение "поймать").Таким образом, добавление «catch» после «cat» означает только один дополнительный узел и еще одну запись в словаре терминала.Структура trie позволяет очень эффективно хранить и индексировать действительно большой список слов.

def _pad(n):
    return " " * n

class Trie(object):
    def __init__(self):
        self.t = {}  # dict mapping symbols to sub-tries
        self.w = {}  # dict listing terminal symbols at this level

    def add(self, word):
        if 0 == len(word):
            return
        cur = self
        for ch in word[:-1]: # add all symbols but terminal
            if ch not in cur.t:
                cur.t[ch] = Trie()
            cur = cur.t[ch]
        ch = word[-1]
        cur.w[ch] = True  # add terminal

    def prefix_match(self, word):
        if 0 == len(word):
            return False
        cur = self
        for ch in word[:-1]: # check all symbols but last one
            # If you check the last one, you are not checking a prefix,
            # you are checking whether the whole word is in the trie.
            if ch in cur.w:
                return True
            if ch not in cur.t:
                return False
            cur = cur.t[ch]  # walk down the trie to next level
        return False

    def debug_str(self, nest, s=None):
        "print trie in a convenient nested format"
        lst = []
        s_term = "".join(ch for ch in self.w)
        if 0 == nest:
            lst.append(object.__str__(self))
            lst.append("--top--: " + s_term)
        else:
            tup = (_pad(nest), s, s_term)
            lst.append("%s%s: %s" % tup)
        for ch, d in self.t.items():
            lst.append(d.debug_str(nest+1, ch))
        return "\n".join(lst)

    def __str__(self):
        return self.debug_str(0)



t = Trie()


# Build valid list from /usr/dict/share/words, which has every letter of
# the alphabet as words!  Only take 2-letter words and longer.

wfile = "/usr/share/dict/words"
for line in open(wfile):
    word = line.strip()
    if len(word) >= 2:
        t.add(word)

# add valid 1-letter English words
t.add("a")
t.add("I")



lst = ["ark", "booze", "kite", "live", "rodeo"]
# "ark" starts with "a"
# "booze" starts with "boo"
# "kite" starts with "kit"
# "live" is good: "l", "li", "liv" are not words
# "rodeo" starts with "rode"

newlst = [w for w in lst if not t.prefix_match(w)]

print(newlst)  # prints: ['live']

Answer 4

Для этого вы должны использовать встроенную функцию lambda.Я думаю, это сделает вашу жизнь намного проще

words = ['rode', 'nick'] # this is the list of all the words that you have.
                         # I'm using 'rode' and 'nick' as they're in your example
listOfWordsToTry = ['rodeo', 'snicker']
def validate(w):
    for word in words:
        if w.startswith(word):
            return False
    return True

wordsThatDontStartWithValidEnglishWords = \
    filter(lambda x : validate(x), listOfWordsToTry)

Это должно работать для ваших целей, если я не понимаю ваш вопрос.

Надеюсь, это поможет

Answer 5

Я считаю, что ответ jkerian является лучшим (при условии, что только один список), и я хотел бы объяснить, почему.

Вот моя версия кода (как функция):

wordlist = ["a","arc","arcane","apple","car","carpenter","cat","zebra"];

def root_words(wordlist):
    result = []
    base = wordlist[0]
    for word in wordlist:
        if not word.startswith(base):
            result.append(base)
            base=word
    result.append(base)
    return result;

print root_words(wordlist);

Пока список слов отсортирован (вы можете сделать это в функции, если хотите), результат будет получен за один раз. Это связано с тем, что при сортировке списка все слова, состоящие из другого слова в списке, будут сразу после этого корневого слова. например все, что попадает между «дугой» и «тайной» в вашем конкретном списке, также будет удалено из-за корневого слова «дуга».

Answer 6

У меня был только один список - и я хотел удалить из него любое слово, которое было префиксом другого.

Вот решение, которое должно выполняться за время O (n log N) и пространство O (M), где M - размер возвращаемого списка. Во время выполнения преобладает сортировка.

l = sorted(your_list)
removed_prefixes = [l[g] for g in range(0, len(l)-1) if not l[g+1].startswith(l[g])] + l[-1:]

• Если список отсортирован, то элемент с индексом N является префиксом, если он начинает элемент с индекса N + 1.

• В конце он добавляет последний элемент исходного отсортированного списка, поскольку по определению он не является префиксом. Обработка этого последнего также позволяет нам перебирать произвольное число индексов без выхода за пределы диапазона.

Если у вас есть запрещенный список, жестко запрограммированный в другом списке:

 banned = tuple(banned_prefixes]
 removed_prefixes = [ i for i in your_list if not i.startswith(banned)]

Это зависит от того факта, что начинается с принятия кортежа. Вероятно, он работает в чем-то близком к N * M, где N - элементы в списке, а M - элементы в banned. Python, возможно, мог бы делать некоторые умные вещи, чтобы сделать это немного быстрее. Если вы похожи на OP и хотите не обращать внимания на кейс, вам понадобятся .lower() звонки местами.

Answer 7

Я не хочу предоставлять точное решение, но я думаю, что в Python есть две ключевые функции, которые вам здесь очень помогут.

Первое упомянутое jkerian: string.startswith () http://docs.python.org/library/stdtypes.html#str.startswith

Второй: фильтр () http://docs.python.org/library/functions.html#filter

С помощью фильтра вы можете написать условную функцию, которая проверит, является ли слово основой другого слова, и вернет true, если это так.

Для каждого слова в списке вам нужно будет выполнить итерации по всем остальным словам и оценить условное выражение, используя фильтр, который может вернуть правильное подмножество корневых слов.