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

Question

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

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

Я думал, что-то вроде этого:

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

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

Answer 1

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

#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 

EDIT: Добавлены некоторые комментарии, чтобы сделать логику более очевидной

Answer 2

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

Для скорости вы должны превратить список допустимых слов в набор. Затем вы можете очень быстро проверить, не найдено ли какое-либо конкретное слово в этом наборе. Затем возьмите каждое слово и проверьте, существуют ли все его префиксы в списке действительных слов или нет. Поскольку слова «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) 

Если вы являетесь поклонником остротами, вы могли бы сделать прочь с для списка и использовать список понимание:

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

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

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

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 3

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

Первый, jkerian отметил: string.startswith() http://docs.python.org/library/stdtypes.html#str.startswith

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

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

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

Answer 4

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

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

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 5

Для этого вам необходимо использовать встроенную функцию 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 6

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

Что, черт возьми, я пошел вперед и написал его.

Вы можете прочитать о здесь синтаксического дерева:

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

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

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

Если вы добавите слово «cat» и слово «catch» в trie, тогда будут узлы для 'c', 'a' и 't' (а также второй 'c' в "поймать"). На уровне узла для «a» словарь «терминалов» будет иметь в нем «t» (таким образом, завершая кодировку «cat»), а также на уровне более глубокого узла второго «c» словарь терминалов будет иметь «h» в нем (завершение «catch»). Итак, добавление «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 7

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

Это решение, которое должно выполняться в 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)] 

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