An Embedded Programmer on a journey to Web Entrepreneurship

If you haven’t heard, Google just released their Instant Search (called “Google Instant”). This gives you search results in real-time, as you type. This is a way of searching that’s becoming increasingly common. In this post, I’ll share some thoughts on the Goolge’s new interface, a few tips and tricks for Power Users, and thoughts on what this might mean for SEO.

Introducing “Search as you Type”

The Basics

Search as you type does exactly what it claims: while typing, Google automatically starts a search for you on the term you’re searching for and displays the results. All without you ever typing “Enter”.

Google doesn’t just start searching for the first letters you type, though; it searches for the best match to what you’re typing (this will come up later when we talk about SEO).

For example, look at the following search:

The black letters are what I’ve typed so far. The gray letters are the letters Google assumes I’ll type next (the best match). As you can see, Google has performed the search based on the best match. Pressing “Enter” will force Google to perform a regular search. In this case, pressing “Enter” will make Google search for “stac”.

Problems with the Interface

Is the fact that Google searches for the best match clear enough? It took someone pointing it out for me to understand how it worked. I’m not sure this will be clear to regular users, negating the benefit of saving people keystrokes. More importantly, I’m worried that people will enter a few letters which have a best match, but will want to perform a search for those letters, and not the best match. Will they realize they need to press “Enter” for Google to do what they want?

A related problem is what happens when a user presses “Enter”. The page is grayed out for a split-second, and then the search is carried out. Does this make it clear what’s going on to users? Or will they enter a few letters (e.g. “tet”), see the results they want (“Tetris”), press “Enter” out of habit, then watch their results disappear.

Interface Features for Power Users

After messing around with the interface for a bit, I found some tricks for Power Users. If you have any more tricks, please list them in the comments.

• Pressing  ”delete” will delete Google’s guess, execute the search, but keep you in the search bar so you can type more text. This is the same as hitting “Enter”, except that “Enter” will cause the search bar to lose focus.
• Typing letters, even when the search bar is out of focus, will type the letters into the search bar. It will even add a space at the end of the last word automatically for you. I love this feature; I’m not sure why they didn’t have it in the old interface. It means I get to keep my hands on the keyboard just a little more than before.
• Hitting “Tab” or the “Right Arrow” will cause Google’s  ”best match” guess to be entered for you. Useful if Google guessed right, but you want to add more search terms.

What Google Instant means for SEO

I’m no SEO expert, and I’m sure that the real impact on SEO won’t be understood for a while. Having said that, the most important Search Engine, by far, has just fundamentally changed the way search works. It’s clear that this will have an impact on SEO. This is obviously something Google has considered long and hard – they’d have to be crazy not to. But human ingenuity will always find a way to take advantage of a new situation, given enough time, and I’m sure this will happen here.

A simple example: best matches for certain letters suddenly become much more important. If I set out looking for a “Volkswagen”, and enter “vol”, I’ll get the following result:

The top ad on the right reads “A Luxury Car means Volvo S40″. Obviously, not the result Volkswagen are hoping for.

In fact, now getting things to be best matches matters a great deal. I’m not even sure there has been work done on understanding the algorithm Google uses for guessing best matches. It doesn’t look like it’s just which search has the most results: “Stack Overflow” has just over 2,000,000 results, while “stack on”, the next best guess, clocks in at 24,000,000.

But just like the search results themselves, how Google decides on a best match will start to be studied and gamed, now that it’s gained such importance.

Conclusion

For me, the bottom line is that I love this move. It’s bold, considering that Google is messing with their most important property. But it’s a step in the right direction – a much better, more modern interface for search. Time will tell how much of an impact this has on SEO, and how the majority of people will take to the new interface. But all things considered, I think Google has done an amazing job.

{ 2 comments }

A Small Riddle

Imagine I have a bucket with an infinite number of dominoes. Each domino looks like one of these:

In other words, I have an infinite number of dominoes which read “a” at the top and “baa” at the bottom, and so on for the other types. The dominoes can’t be turned end for end: they have a specific top and bottom (otherwise the letters would be upside down, which is obviously crazy).

Here’s the riddle: try to arrange the dominoes, in any order you like, so that the string made of all the tops of the dominoes and the string made of all the bottoms of the dominoes is the same string.

The simplest attempt is to take one of each kind of domino and arrange them in order, as in the picture above. Reading all the tops of the dominoes gives the string “a,ab,bba”, and the bottoms read “baa,aa,bb”, which are obviously not the same string (I added the commas for clarity, but the comparison is done without them).

Is it possible to find an arrangement with those three types dominoes to get an answer? The solution, in this case, is the following:

If we number the original dominoes 1-3, this solution has the sequence: 3-2-3-1, and the strings read: “bba,ab,bba,a” and “bb,aa,bb,baa”. Without the commas, both strings read: “bbaabbbaa”. Not too difficult.

The General Problem

Now comes the interesting part. I could ask you the same question, but give you a different set of dominoes. For example, I could give you the same set as before, but without the third domino:

It’s pretty clear that in this case, no solution is possible. If I start with the first domino, already the strings are different, since one starts with an “a” and the other with a “b”. Likewise, starting with the second domino gives us a top string that starts “ab” and a bottom string that starts “aa”, so once again, we are stuck.

So the general question becomes, given a set of dominoes, is there a way to solve the problem by forming two equal strings? In other words:

Given a set of domino types, return True if the problem can be solved (i.e., the dominoes can be arranged to form two equal strings), or False otherwise.

Take a few minutes to try and come up with the algorithm that solves this. But don’t try for too long; this is a deceptively difficult problem.

The Solution

Okay, I lied a little. This isn’t a difficult problem; it’s an impossible one. There is no possible algorithm which solves the general case of the Correspondence Problem, as was proved by Emil Post in 1946.

The proof of the undecidability of the Post Correspondence Problem is a complicated one. I learned it from Sipser’s Introduction to the Theory of Computation (affiliate). It involves showing that any Turing Machine can be simulated by carefully constructing the dominoes, making solving the Post Correspondence Problem equivalent to checking whether a Turing Machine accepts a given input. Since the latter is provably undecidable, the former must be undecidable as well.

Why I love the Post Correspondence Problem

I love the field of Computer Science, and I really love questions about decidability. It seems magical  to me that some problems can never be solved by an algorithm. But most of the time, the undecidable problems (like the famous Halting Problem), seem a little detached from actual programming.

The reason I love the Post Correspondence Problem is that this seems like it should have an answer. When I first heard about it, I spent a lot of time looking for an algorithm to solve this, before learning that no algorithm can exist. This is the type of problem I can imagine running into during my day to day programming, and trying to solve it without realizing that it can’t be solved.

Which leads me to wonder: how many times have programmers working on real-life programs stumbled onto unsolvable problems, and tried to attack them without realizing the futility?

{ 16 comments }