Language-Agnostic Search

robk — Thu, 26 Feb 2009 22:56:00 GMT

Some of the demos featured in TechFest 2009 were submitted by the Cairo Microsoft Innovation Center, and i got a chance to speak with a couple of Cairo researchers, Kareem Darwish and Motaz El-Saban, about their work.

"We're trying to enable multilingual search," Darwish said, "in the space of text documents and in the space of printed documents. In the case of printed documents, this is the OCRLess."

Then El-Saban took over.

"OCRLess is about language-independent technology," he said, "that allows you to search within scanned document images without the use of OCR (optical character recognition). Traditionally, if you have a document image, you would need to convert it into text using OCR, and then you can search. What we do as an alternative approach is take the text query and transform it into an image for rendering. Then we match it against the image document. It's based on image matching and indexing, and what we're showing here is five languages--English, Arabic, Chinese, Hebrew, and hieroglyphics."

Hieroglyphics ready to be searched.

It's an ingenious approach, upon which El-Saban expanded.

"The first step is to segment it," he explained. "The segment can be a character, a part of a character, or a word. in English, it's a character. We take all these segments and cluster similar shapes together in a completely unsupervised manner, then assign an ID to each cluster. Now, every page is presented, instead of by the characters, by a set of IDs, and we index this set of IDs into a regular search engine. With a query, we do the same thing. We render it into an image using the font of the book, then we segment it into pieces, and we actually assign, for each piece, the closest cluster ID.The query is a string of IDs, basically, and we go search for the string in the book. This makes it effective, because we're using image matching, and efficient, becomes we're using an underlying basic search engine.When we actually match the image query to an image inside the book, we're using template matching, an array of pixels."

So where might this work lead?

"There are a number of possibilities," El-Saban said. "Libraries could use something like this, or whatever entities sit on large volumes of documents, possibly written in many languages, for which you don't have an OCR. Another area of potential is handwriting search. You write your own notes by hand, and then, without even having to recognize your handwriting, you can still search them. I'm trying to sit with different contacts in Microsoft product groups to see if there is an interest to take this project in a specific direction."

Back to Darwish, whose project is called Trans-Bulletization.

"We're trying to enable people to search using English queries against documents in many, many different languages," he says, "and then present the results, not in the original language of the documents, but in a bulletized list, a summary that removes superfluous words from the English translation and puts the information into bulletized form. The user then can very quickly learn what the document is about and consequently make a decision whether they want to invest more time reading the full translation or the original document."

He went on to discuss how entire documents are boiled down to bulleted lists.

"The key technology is all the documents we are going to search, we translate into English first, and then deploy the bulletized technique," Darwish said.."Actually, it's a sentence-reduction technique. To reduce the sentences, we use a dependency parser that recognizes the main verb, the subject of this verb, and the object. Given that these are the core components of the sentence, then we find all the other pieces--prepositional phrases, modifiers, and so forth--then make a judgment about the information content of these pieces. If they have low information content, then they're candidates for removal, but before we remove them, we have to make sure that they don't break anything in the sentence. We won't remove a noun phrase unless that, if we remove it, it won't break the flow as measured by language models."

Such help could provide a boon to many in this information-saturated age.

"For people who work in an organization that requires sifting through a lot of documents in many, many languages, this would be really useful," Darwish concludes. "They're getting all the information content in a shortened version, so they can scan lots of documents very, very quickly. A typical user might be a reporter who wants to see how people look at a particular issue across different countries. As the person enters a query across the countries he's interested in, he gets articles from Japan, the Middle East, from China and Europe, and so forth, and then he can see all the different views at the same time, in bulleted lists. He can do this very, very efficiently and very, very quickly."

Motaz El-Saban (left) and Kareem Darwish in their TechFest booth.

TechFest Live! : Center

Language-Agnostic Search