[RESOLVED] How to select similar text entries?

[void_function]

Hello!

I have a table with a client name column, and in a form, I need to select a client by supplying his full name, or if s/he doesn't exist, showing clients with similar names so that the user can select from a list.

That I can resolve with a simple WHERE name="$name", the 'name' column being indexed.

But here comes the problem. When such select yields 0 entries, I want to find SIMILAR names, matching as much of characters from the left as possible. For example, if I'm looking for "John Doe", I want the script, failing to find him, to show me similars like:

Johan Doe
Johen Doe
John Doae
...

I don't know if MySQL has a string comparison function that would do this, so I decided to make an algorithm:

If WHERE name=$name fails, then I'd do multiple selects, in a loop, like this:

1st iteration: name LIKE "J%"
2nd iteration: name LIKE "Jo%"
3rd: name LIKE "Joh%"
...

until an iteration finds 0 results, for example at "John%"

Then, I'd go one step back ("Joh%") and select all results where name LIKE "Joh%". Of course, instead of retrieving entire sets of rows matching the query, I'd only COUNT(*) them and stop when count is 0 and then go one step back (by remembering last matching string), and then I'd select full set of rows.

I hope I explained this well. Any comments, or easier solutions? Thanks in advance.

[leatherback]

Is this part of a login on a public website? Then I would not use this system. It is pretty much inviting a hacker to come in.

Anyway. A function does exist that will do a matching. (Not sure, maybe the argument is even called match..?). But i am not sure. This topic has come up about 4 weeks ago, maybe you can find it on the forum, hope for somebody to know it, or look at mysql.com

[void_function]

Of course, it is not a part of public login page. 🙂 It's paperwork administration application where the user must select unique client to associate with particular document. Unique meaning, there can be only one entry per client (in clients' table), to avoid typos when supplying names. But there can be two clients with same name, having different address or other parameters. And when then name is not sure, you just supply first few letters or something, and the application supplies all names according to the algorithm just described above.

MATCH ... AGAINST, is part of fulltext search, and it matches only direct hits, not similars. Besides, fulltext is not an option, as it is somewhat probabilistic in behaviour.

I've scaned mysql documentation, particularly string comparison functions, but can't seem to find what I need (am I missing something?). I've also searched this board, but found none relevant topics.

EDIT: To be precise, what I need actually is, when supplied name is not found, an algorithm that would return all names that share some common character string with the supplied name, starting from the left. In the above example, that string appears to be "Joh". That's what I need.

Cheers,

void();

[mrhappiness]

if possible, create your own udf (user defined function): http://empyrean.lib.ndsu.nodak.edu/~nem/mysql/udf/ (leventshein is the one to look for)

or you try using SOUNDEX:
maybe it's possible to convert the first character returned by SOUNDEX into its ascii-code, add it to the remaining 3 characters and then subtract both soundex-representations from each other and use that for ORDER BY?

or you try MATCH AGAINST IN BOOLEAN MODE and edit the searchstring before sending it to mysql

[mrhappiness]

or you do something like that

$order_by = array();
$search = 'Jon Doe';
while (!empty($search)) {
	$order_by[] = "LOCATE('".$search."', the_column) != 0";
	$search = substr($search, 0, -1);
}

if (count($order_by))
	$order_by = "ORDER BY FIND_IN_SET('1', CONCATE_WS(',', ".implode(', ', $order_by).'))';
else
	$order_by = '';

$sql = 'SELECT the_column
FROM the_table
'.$order_by;

output:

SELECT the_column
FROM the_table
ORDER BY FIND_IN_SET('1', CONCATE_WS(',', 
  LOCATE('Jon Doe', the_column) != 0, 
  LOCATE('Jon Do', the_column) != 0, 
  LOCATE('Jon D', the_column) != 0, 
  LOCATE('Jon ', the_column) != 0, 
  LOCATE('Jon', the_column) != 0, 
  LOCATE('Jo', the_column) != 0, 
  LOCATE('J', the_column) != 0))

this should order the entries by the amount of characters that are identical with the search string starting from the left

[leatherback]

Or use a javascript function:

Get all the names from the database, and have a textbox for the user to type in the letters. This javascript will then re-populate the dropdownbox, based on matches. For a locally runnin app. this should not be too load-intyensive:

<?php 

//select

$query1 = mysql_query("SELECT ....."); 

	WHILE($row = mysql_fetch_array($query1)) 
  	 {
    	 $list .= "<option value=\"".$row['ID']."\">".$row['Name']."</option>"; 
     } 
?> 

<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1" x-undefined>

<script language="JavaScript" type="text/javascript">
<!--



function FilterList(pattern,listname)
  {
  pattern = new RegExp('^'+pattern,"i"); 
  i=0;
  sel=0;

  while(i<listname.options.length)
   {
   if(pattern.test(listname.options[i].text))
     {
      sel=i;
      break
     }          

    i++;
    }
    listname.options.selectedIndex=sel;
  }
// -->
</script>
</head>


<body>
    <FORM name='Form1' method="GET" action= "select_species.php">
    <input type="text" name="yourTextField" onkeyup="FilterList(this.value,this.form.name);">
    <select name="name">
    <option value="">Select a name</option>";
       <? echo $list; ?>
    </select>
    <input type= submit>


</form>

</body>

</html>

[superwormy]

SOUNDEX() ( both PHP and MySQL have this function I think ) or metaphone ( www.php.net/metaphone ) are definitally your best bet.

metaphone() is much nicer than soundex usually.

[void_function]

Thanks for your replies guys.

mrhappiness' example could be the best alternative. In both cases, the algorithm apparently needs multiple selects, the maximum number thereof is the numer of letters in the name (no bigger than 64 which is the column size). Practically, though, there will be small number of queries per name, as either the name is found directly, or there are only a few letters (few queries) that similar names share.

Javascript solution of feeding all names into a textbox would be ok for a small number of names, however I expect more than 10000 clients in the database, and the number of names starting with the same letter could get quite substantial - not an option to send all back to browser.

Soundex and metaphone are not good as they can miss certain names, and it is crucial that I present all names sharing same substring starting from the first letter.

Again, thanks. The problem has been solved. 🙂