You Mean | Frontier Nerds

Concept

Google’s automatic search completion give an instant zeitgeist from just a few words of input. Here’s an example of it at work:

Google search box with autocompletion menu open

A universal auto-complete function would be a useless and wonderful thing to have, and right now I think Google’s search completion is as close as we can get. I’m interested in what would happen if a piece of text was forced to conform with Google’s platonic search query, essentially handing over final editorial authority the their algorithm — which in itself is just a representation of grooves worn into the search engine by millions of people searching for exactly the same thing.

Google sometimes imposes their assistance by placing a link at the top of search results suggesting “did you mean something?” This officious interjection is often creepily right — why yes, I did mean something.

Hence my proposed poetic form: You Mean. This form takes Google’s help a step further by forcing a given string through the suggestion algorithm and reconstructing output consisting entirely of suggestions.

For example, the paragraph above becomes the following:

Henceforth myspace proposed health care bill poetic forms you mean the world to me this form is submitted in connection with an application for takeshi kaneshiro google scholar help a reporter out step further or farther byu forcing amaryllis longest palindrome in a given string through the looking glass suggestion algorithms andkon reconstructing history output devices consisting essentially of entirely pets office depot suggestions lyrics.

Demo

Algorithm

First, I needed programmatic access to Google’s suggestions. Google itself was helpful enough to point me to this gentle hack of their toolbar code — a URL that you can hit for an XML list of suggestions for a given query. Handy.

Next, there was the issue of how to atomize input text. This proved a bit trickier, since judgments would have to be made as to how much of a line should be fed through the algorithm at a time. Initially, I tried sending words in individually. This was helpful in creating repetitive structures in the output, but I thought it was loosing to much of the source text’s content.

So I implemented a recursive algorithm that takes the full text of a line, and then tests to see if there are suggestions for it. If there are suggestions, it declares success. If not, it pops a word off the end up the sentence, and tries to find a suggestion for the new, shorter line. It continues to pop words until it finds a suggestion, and then will return to the rest of the sentence and go through the same process of shortening until a suggestion is found. Eventually, a whole line is digested this way. It unfairly weights the beginning of the line (since it’s tested first) but it seemed like a reasonable compromise between performance (the http queries take some time) and content retention.

With some extra print statements, processing looks like this — showing the recursive approach to suggested-sentence generation:

You say: showing the recursive approach
trying: showing the recursive approach
no suggestions
trying: showing the recursive
no suggestions
trying: showing the
suggestion: shown thesaurus
trying: recursive approach
no suggestions
trying: recursive
suggestion: recursive formula
trying: approach
suggestion: approach plates
You mean: shown thesaurus recursive formula approach plates

Occasionally, Google gets stumped on a single word and runs out of suggestions. (“Pluckiest”, for example.) In these cases, the algorithm relents and lets the original word through. It’s conceivable that an entire body of text could elude suggestions in this way, if the words were far enough from the online vernacular.

Output

An interesting behavior emerges in canonical texts. Partial lines will be automatically completed with the original text, which gives the text a tendency to repeat itself.

For example, here’s Frost:

whose woods these are i think i know his house is in the village though
his house is in the village though thought for the day
he will not see me stopping here to watch his woods fill up with snow
to watch his woods fill up with snow snowshoe mountain
my little horse must think it queer to stop without a farmhouse near
to stop without a farmhouse near near death experiences
between the woods and frozen lake the darkest evening of the year
the darkest evening of the year by dean koontz
he gives his harness bells a shake to ask if there is some mistake
to ask in spanish if there is something lyrics mistake quotes
the only other sound’s the sweep sounds the same spelled differently sweepstakes
of easy wind and downy flake flake lyrics
the woods are lovely dark and deep poem
but i have promises to keep and miles to go before i sleep
and miles to go before i sleep meaning
and miles to go before i sleep meaning

Source Code

The code is designed to work in two possible configurations. You can either pass it text via standard input, which it will suggestify and spit back out. Or, you can run it with the argument “interactive”, which will bring up a prompt for you to experiment quickly with different suggested text transformations.

import sys
import urllib
from xml.dom import minidom
import string

# set to true for more output
debug = 0

def strip_punctuation(s):
	return s.translate(string.maketrans("",""), string.punctuation)

# returns a list of google suggestions

# store them in a dictionary for basic caching... then when parsing the text
# fetch the suggestion from google only if we need to
suggestion_cache = dict();

def fetch_suggestions(query):
	if query in suggestion_cache:
		return suggestion_cache[query]

	# here's the suggestion "API"
	# google.com/complete/search?output=toolbar&q=microsoft
	# adding a trailing space prevents partial matches
	# how to handle multi-word? find the largest possible suggestions
	query_string = urllib.urlencode({"output" : "toolbar", "q" : query})	
	
	# returns some xml
	suggestion_request = urllib.urlopen("http://www.google.com/complete/search?" + query_string)
	
	suggestions = list();	
		
	# handle the odd xml glitch from google
	try:
		suggestion_xml = minidom.parse(suggestion_request)
		# let's extract the suggestions (throw them in a list)
		for suggestion in suggestion_xml.getElementsByTagName("suggestion"):
			suggestions.append(suggestion.attributes["data"].value)

		suggestion_cache[query] = suggestions;
	except:
		pass
	
	suggestion_request.close()
	
	return suggestions


# glues together a list of words into a sentence based on start and end indexes
def partial_sentence(word_list, start, end):
	if len(word_list) >= end:	
		sentence = str()
		for i in range(start, end):
			sentence = sentence + word_list[i] + " "
	
		return sentence.strip()
	else:
		return "partial sentence length error"


# takes a line and recursively returns google's suggestion
def suggestify_line(line):
	output_text = ""	
	words = line.lower().strip().split(" ")

	if len(words) > 1:

		end_index = len(words)
		start_index = 0
		suggested_line = ""
		remaining_words = len(words)
	
		# try to suggest based on as much of the original line as possible, then
		# walk left to try for matches on increasingly atomic fragments
		while remaining_words > 0:
			query = partial_sentence(words, start_index, end_index)
			suggestions = fetch_suggestions(query)
	
			if debug: print "trying: " + query
	
			if suggestions:
				if debug: print "suggestion: " + suggestions[0]
				output_text += suggestions[0] + " "
				
				remaining_words = len(words) - end_index
				start_index = end_index;
				end_index = len(words)
		
			else:
				# else try a shorter query length		
				if debug: print "no suggestions"
				
				# if we're at the end, relent and return original word 
				if (end_index - start_index) == 1:
					if debug: print "no suggestions, using: " + words[start_index]
					output_text += words[start_index] + " "
					remaining_words = len(words) - end_index
					start_index = end_index;
					end_index = len(words)					
				else:
					end_index -= 1

	# handle single word lines
	elif len(words) == 1:
		if debug: print "trying: " + words[0]		
		suggestions = fetch_suggestions(words[0])
		if suggestions:
			if debug: print "suggestion: " + suggestions[0]
			output_text += suggestions[0] + " ";			
		else:
			if debug: print "defeat"
			# defeat, you get to use the word you wanted
			if debug: print words[0]
			output_text += words[0] + " ";			
	
	output_text.strip()
	return output_text



# are we in interactive mode?

if len(sys.argv) <= 1:
	# Grab a file from standard input, dump it in a string.
	# source_text = sys.stdin.readlines()
	source_text = open("frost.txt").readlines()
	#source_text = "His house is in the village though"

	output_text = ""

	for line in source_text:
		output_text += suggestify_line(strip_punctuation(line))
		output_text += "\n"

	print output_text


elif sys.argv[1] == "interactive":
	while 1:
		resp = raw_input("You say: ")
		print "You mean: " + suggestify_line(strip_punctuation(resp)) + "\n"
		if resp == "exit":
			break

import sys
import urllib
from xml.dom import minidom
import string

# set to true for more output
debug = 0

def strip_punctuation(s):
	return s.translate(string.maketrans("",""), string.punctuation)

# returns a list of google suggestions

# store them in a dictionary for basic caching... then when parsing the text
# fetch the suggestion from google only if we need to
suggestion_cache = dict();

def fetch_suggestions(query):
	if query in suggestion_cache:
		return suggestion_cache[query]

	# here's the suggestion "API"
	# google.com/complete/search?output=toolbar&q=microsoft
	# adding a trailing space prevents partial matches
	# how to handle multi-word? find the largest possible suggestions
	query_string = urllib.urlencode({"output" : "toolbar", "q" : query})

	# returns some xml
	suggestion_request = urllib.urlopen("http://www.google.com/complete/search?" + query_string)

	suggestions = list();

	# handle the odd xml glitch from google
	try:
		suggestion_xml = minidom.parse(suggestion_request)
		# let's extract the suggestions (throw them in a list)
		for suggestion in suggestion_xml.getElementsByTagName("suggestion"):
			suggestions.append(suggestion.attributes["data"].value)

		suggestion_cache[query] = suggestions;
	except:
		pass

	suggestion_request.close()

	return suggestions


# glues together a list of words into a sentence based on start and end indexes
def partial_sentence(word_list, start, end):
	if len(word_list) >= end:
		sentence = str()
		for i in range(start, end):
			sentence = sentence + word_list[i] + " "

		return sentence.strip()
	else:
		return "partial sentence length error"


# takes a line and recursively returns google's suggestion
def suggestify_line(line):
	output_text = ""
	words = line.lower().strip().split(" ")

	if len(words) > 1:

		end_index = len(words)
		start_index = 0
		suggested_line = ""
		remaining_words = len(words)

		# try to suggest based on as much of the original line as possible, then
		# walk left to try for matches on increasingly atomic fragments
		while remaining_words > 0:
			query = partial_sentence(words, start_index, end_index)
			suggestions = fetch_suggestions(query)

			if debug: print "trying: " + query

			if suggestions:
				if debug: print "suggestion: " + suggestions[0]
				output_text += suggestions[0] + " "

				remaining_words = len(words) - end_index
				start_index = end_index;
				end_index = len(words)

			else:
				# else try a shorter query length
				if debug: print "no suggestions"

				# if we're at the end, relent and return original word
				if (end_index - start_index) == 1:
					if debug: print "no suggestions, using: " + words[start_index]
					output_text += words[start_index] + " "
					remaining_words = len(words) - end_index
					start_index = end_index;
					end_index = len(words)
				else:
					end_index -= 1

	# handle single word lines
	elif len(words) == 1:
		if debug: print "trying: " + words[0]
		suggestions = fetch_suggestions(words[0])
		if suggestions:
			if debug: print "suggestion: " + suggestions[0]
			output_text += suggestions[0] + " ";
		else:
			if debug: print "defeat"
			# defeat, you get to use the word you wanted
			if debug: print words[0]
			output_text += words[0] + " ";

	output_text.strip()
	return output_text



# are we in interactive mode?

if len(sys.argv) <= 1:
	# Grab a file from standard input, dump it in a string.
	# source_text = sys.stdin.readlines()
	source_text = open("frost.txt").readlines()
	#source_text = "His house is in the village though"

	output_text = ""

	for line in source_text:
		output_text += suggestify_line(strip_punctuation(line))
		output_text += "\n"

	print output_text


elif sys.argv[1] == "interactive":
	while 1:
		resp = raw_input("You say: ")
		print "You mean: " + suggestify_line(strip_punctuation(resp)) + "\n"
		if resp == "exit":
			break