List all words in a dictionary that start with <user input>
How would a go about making a program where the user enters a string, and the program generates a list of words beginning with that string?
Ex:
User: "abd"
Program:abdicate, abdomen, abduct...
Thanks!
Edit: I'm using python, but I assume that this is a fairly language-independent problem.
Asked by: Freddie792 | Posted: 28-01-2022
Answer 1
Use a trie.
Add your list of words to a trie. Each path from the root to a leaf is a valid word. A path from a root to an intermediate node represents a prefix, and the children of the intermediate node are valid completions for the prefix.
Answered by: Fenton927 | Posted: 01-03-2022Answer 2
One of the best ways to do this is to use a directed graph to store your dictionary. It takes a little bit of setting up, but once done it is fairly easy to then do the type of searches you are talking about.
The nodes in the graph correspond to a letter in your word, so each node will have one incoming link and up to 26 (in English) outgoing links.
You could also use a hybrid approach where you maintain a sorted list containing your dictionary and use the directed graph as an index into your dictionary. Then you just look up your prefix in your directed graph and then go to that point in your dictionary and spit out all words matching your search criteria.
Answered by: Kelvin717 | Posted: 01-03-2022Answer 3
If you on a debian[-like] machine,
#!/bin/bash
echo -n "Enter a word: "
read input
grep "^$input" /usr/share/dict/words
Takes all of 0.040s on my P200.
Answered by: Clark350 | Posted: 01-03-2022Answer 4
egrep `read input && echo ^$input` /usr/share/dict/words
oh I didn't see the Python edit, here is the same thing in python
my_input = raw_input("Enter beginning of word: ")
my_words = open("/usr/share/dict/words").readlines()
my_found_words = [x for x in my_words if x[0:len(my_input)] == my_input]
Answer 5
If you really want speed, use a trie/automaton. However, something that will be faster than simply scanning the whole list, given that the list of words is sorted:
from itertools import takewhile, islice
import bisect
def prefixes(words, pfx):
return list(
takewhile(lambda x: x.startswith(pfx),
islice(words,
bisect.bisect_right(words, pfx),
len(words)))
Note that an automaton is O(1) with regard to the size of your dictionary, while this algorithm is O(log(m)) and then O(n) with regard to the number of strings that actually start with the prefix, while the full scan is O(m), with n << m.
Answered by: Alberta744 | Posted: 01-03-2022Answer 6
def main(script, name):
for word in open("/usr/share/dict/words"):
if word.startswith(name):
print word,
if __name__ == "__main__":
import sys
main(*sys.argv)
Answer 7
If you really want to be efficient - use suffix trees or suffix arrays - wikipedia article.
Your problem is what suffix trees were designed to handle. There is even implementation for Python - here
Answered by: Ryan528 | Posted: 01-03-2022Answer 8
You can use str.startswith(). Reference from the official docs:
str.startswith(prefix[, start[, end]])
Return True if string starts with the prefix, otherwise return False. prefix can also be a tuple of prefixes to look for. With optional start, test string beginning at that position. With optional end, stop comparing string at that position.
try code below:
dictionary = ['apple', 'abdicate', 'orange', 'abdomen', 'abduct', 'banana']
user_input = input('Enter something: ')
for word in dictionary:
if word.startswith(user_input):
print(word)
Output:
Enter something: abd
abdicate
abdomen
abduct
Answer 9
var words = from word in dictionary
where word.key.StartsWith("bla-bla-bla");
select word;
Answer 10
Try using regex to search through your list of words, e.g. /^word/ and report all matches.
Answered by: Aida134 | Posted: 01-03-2022Answer 11
If you need to be really fast, use a tree:
build an array and split the words in 26 sets based on the first letter, then split each item in 26 based on the second letter, then again.
So if your user types "abd" you would look for Array[0][1][3] and get a list of all the words starting like that. At that point your list should be small enough to pass over to the client and use javascript to filter.
Answered by: Sawyer119 | Posted: 01-03-2022Answer 12
Most Pythonic solution
# set your list of words, whatever the source
words_list = ('cat', 'dog', 'banana')
# get the word from the user inpuit
user_word = raw_input("Enter a word:\n")
# create an generator, so your output is flexible and store almost nothing in memory
word_generator = (word for word in words_list if word.startswith(user_word))
# now you in, you can make anything you want with it
# here we just list it :
for word in word_generator :
print word
Remember generators can be only used once, so turn it to a list (using list(word_generator)) or use the itertools.tee function if you expect using it more than once.
Best way to do it :
Store it into a database and use SQL to look for the word you need. If there is a lot of words in your dictionary, it will be much faster and efficient.
Python got thousand of DB API to help you do the job ;-)
Answered by: Oliver226 | Posted: 01-03-2022Answer 13
If your dictionary is really big, i'd suggest indexing with a python text index (PyLucene - note that i've never used the python extension for lucene) The search would be efficient and you could even return a search 'score'.
Also, if your dictionary is relatively static you won't even have the overhead of re-indexing very often.
Answered by: Blake556 | Posted: 01-03-2022Answer 14
Don't use a bazooka to kill a fly. Use something simple just like SQLite. There are all the tools you need for every modern languages and you can just do :
"SELECT word FROM dict WHERE word LIKE "user_entry%"
It's lightning fast and a baby could do it. What's more it's portable, persistent and so easy to maintain.
Python tuto :
http://www.initd.org/pub/software/pysqlite/doc/usage-guide.html
Answered by: First Name116 | Posted: 01-03-2022Answer 15
A linear scan is slow, but a prefix tree is probably overkill. Keeping the words sorted and using a binary search is a fast and simple compromise.
import bisect
words = sorted(map(str.strip, open('/usr/share/dict/words')))
def lookup(prefix):
return words[bisect.bisect_left(words, prefix):bisect.bisect_right(words, prefix+'~')]
>>> lookup('abdicat')
['abdicate', 'abdication', 'abdicative', 'abdicator']
Answer 16
If you store the words in a .csv file, you can use pandas to solve this rather neatly, and after you have read it once you can reuse the already loaded data frame if the user should be able to perform more than one search per session.
df = pd.read_csv('dictionary.csv')
matching_words = df[0].loc[df[0].str.startswith(user_entry)]
Similar questions
python, dictionary and int error
I have a very frustrating python problem. In this code
fixedKeyStringInAVar = "SomeKey"
def myFunc(a, b):
global sleepTime
global fixedKeyStringInAVar
varMe=int("15")
sleepTime[fixedKeyStringInAVar] = varMe*60*1000
#more code
Now this works. BUT sometimes when I run this function I get
TypeError: 'int' object does not support item assignment
python - Best way to create a NumPy array from a dictionary?
I'm just starting with NumPy so I may be missing some core concepts...
What's the best way to create a NumPy array from a dictionary whose values are lists?
Something like this:
d = { 1: [10,20,30] , 2: [50,60], 3: [100,200,300,400,500] }
Should turn into something like:
data = [
[10,20,30,?,?],
[50,60,?,?,?],
[100,200,300,400,500]
]
...
python - List a dictionary
In a list appending is possible. But how I achieve appending in dictionary?
Symbols from __ctype_tab.o:
Name Value Class Type Size Line Section
__ctype |00000000| D | OBJECT|00000004| |.data
__ctype_tab |00000000| r | OBJECT|00000101| |.rodata
Symbols from _ashldi3.o:
Name Value Class ...
python - How to filter a dictionary by value?
Newbie question here, so please bear with me.
Let's say I have a dictionary looking like this:
a = {"2323232838": ("first/dir", "hello.txt"),
"2323221383": ("second/dir", "foo.txt"),
"3434221": ("first/dir", "hello.txt"),
"32232334": ("first/dir", "hello.txt"),
"324234324": ("third/dir", "dog.txt")}
I want all values that are equal to each other to be moved into...
Python and dictionary like object
I need a python 3.1 deep update function for dictionaries (a function that will recursively update child dictionaries that are inside a parent dictionary).
But I think, in the future, my function could have to deal with objects that behave like dictionaries but aren't. And furthermore I want to avoid using isinstance and type (because they are considered b...
python - Remove dictionary from list
If I have a list of dictionaries, say:
[{'id': 1, 'name': 'paul'},
{'id': 2, 'name': 'john'}]
and I would like to remove the dictionary with id of 2 (or name 'john'), what is the most efficient way to go about this programmatically (that is to say, I don't know the index of the entry in the list so it can't simply be popped).
C# way to mimic Python Dictionary Syntax
Is there a good way in C# to mimic the following python syntax:
mydict = {}
mydict["bc"] = {}
mydict["bc"]["de"] = "123"; # <-- This line
mydict["te"] = "5"; # <-- While also allowing this line
In other words, I'd like something with [] style access that can return either another dictionary or a string type, depending on how it has been set.
I've been trying to work...
python - Can a dictionary be passed to django models on create?
Is it possible to do something similar to this with a list, dictionary or something else?
data_dict = {
'title' : 'awesome title',
'body' : 'great body of text',
}
Model.objects.create(data_dict)
Even better if I can extend it:
Model.objects.create(data_dict, extra='hello', extra2='world')
python - Make Dictionary From 2 List
This question already has answers here:
Python dictionary simple way to add a new key value pair
Say you have,
foo = 'bar'
d = {'a-key':'a-value'}
And you want
d = {'a-key':'a-value','foo':'bar'}
e = {'foo':foo}
I know you can do,
d['foo'] = foo
#Either of the following for e
e = {'foo':foo}
e = dict(foo=foo)
But, in all these way to add the variable foo to dict, I have had to use the word foo twice; onc...
sorting - In Python, how can you easily retrieve sorted items from a dictionary?
Dictionaries unlike lists are not ordered (and do not have the 'sort' attribute). Therefore, you can not rely on getting the items in the same order when first added.
What is the easiest way to loop through a dictionary containing strings as the key value and retrieving them in ascending order by key?
For example, you had this:
d = {'b' : 'this is b', 'a': 'this is a' , 'c' : 'this is c'}
Python dictionary from an object's fields
Do you know if there is a built-in function to build a dictionary from an arbitrary object? I'd like to do something like this:
>>> class Foo:
... bar = 'hello'
... baz = 'world'
...
>>> f = Foo()
>>> props(f)
{ 'bar' : 'hello', 'baz' : 'world' }
NOTE: It should not include methods. Only fields.
python - How do you retrieve items from a dictionary in the order that they're inserted?
Is it possible to retrieve items from a Python dictionary in the order that they were inserted?
python - How can I make a dictionary from separate lists of keys and values?
I want to combine these:
keys = ['name', 'age', 'food']
values = ['Monty', 42, 'spam']
Into a single dictionary:
{'name': 'Monty', 'age': 42, 'food': 'spam'}
python - Dictionary or If statements, Jython
I am writing a script at the moment that will grab certain information from HTML using dom4j.
Since Python/Jython does not have a native switch statement I decided to use a whole bunch of if statements that call the appropriate method, like below:
if type == 'extractTitle':
extractTitle(dom)
if type == 'extractMetaTags':
extractMetaTags(dom)
Is a Python dictionary an example of a hash table?
One of the basic data structures in Python is the dictionary, which allows one to record "keys" for looking up "values" of any type. Is this implemented internally as a hash table? If not, what is it?
python - Is there a "one-liner" way to get a list of keys from a dictionary in sorted order?
The list sort() method is a modifier function that returns None.
So if I want to iterate through all of the keys in a dictionary I cannot do:
for k in somedictionary.keys().sort():
dosomething()
Instead, I must:
keys = somedictionary.keys()
keys.sort()
for k in keys:
dosomething()
Is there a pretty way to iterate t...
python - Interface to versioned dictionary
I have an versioned document store which I want to access through an dict like interface.
Common usage is to access the latest revision (get, set, del), but one should be able to access specific revisions too (keys are always str/unicode or int).
from UserDict import DictMixin
class VDict(DictMixin):
def __getitem__(self, key):
if isinstance(key, tuple):
docid, rev = key
e...
python - Check if a given key already exists in a dictionary and increment it
How do I find out if a key in a dictionary has already been set to a non-None value?
I want to increment the value if there's already one there, or set it to 1 otherwise:
my_dict = {}
if my_dict[key] is not None:
my_dict[key] = 1
else:
my_dict[key] += 1
Given a list of variable names in Python, how do I a create a dictionary with the variable names as keys (to the variables' values)?
I have a list of variable names, like this:
['foo', 'bar', 'baz']
(I originally asked how I convert a list of variables. See Greg Hewgill's answer below.)
How do I convert this to a dictionary where the keys are the variable names (as strings) and the values are the values of the variables?
{'foo': foo, 'bar': bar, 'baz': baz}
Now that I'm re-aski...
Still can't find your answer? Check out these communities...
PySlackers | Full Stack Python | NHS Python | Pythonist Cafe | Hacker Earth | Discord Python