Created attachment 254 [details]
Patch to provide a form of predictive text searching to SlimServer.

This patch is against the 10th January 2005 nightly build of 5.4.1.

The following is a description of the approach and patch; it's a bit verbose,
but I've just copied it from my webpage
(http://hickinbottom.demon.co.uk/SlimServer/lazy_searching.htm).
-------
Lazy Searching with the Squeezebox Remote 

Aim

The idea is to allow searching for something like "PINK FLOYD" with less key
presses on the Squeezebox remote. As an example, this artist search takes 22
key presses (not including navigating to "Search Artists" or initiating the
search). There must be a better way! 

Mobile phones have addressed this in recent times. One way is utilising
so-called predictive text, which aims to complete words against an internal
dictionary while also trying to guess what each letter was supposed to be
(alleviating the need to press the "2" key twice to enter a "B", for example). 

Given that the SlimServer already has a pretty good built-in dictionary (the
music database it has scanned), it should be able to do something similar. 

I must admit that I didn't come up with this idea completely by myself - I've
developed this in response to the following enhancement request:
https://bugs-archive.lyrion.org/show_bug.cgi?id=386

Although this solution isn't exactly what the originator had in mind (it
doesn't narrow as you type in the search as mobile phones do), it's been a
reasonably straightforward implementation and does result in a significantly
reduced number of button-presses compared with the traditional method. 

Because this isn't quite "predictive" in the mobile phone sense, I just call
this lazy searching because it saves having to make multiple taps to get to
subsequent letters on the remote. 

The solution and implementation of this this idea proved surprisingly simple,
as explained below. 

Principles
The basic idea is to avoid the user having to press each key multiple times to
select the correct character - twice to enter "B", for example. As a simple
example, consider "ABBA" - this currently takes six key presses for a
four-letter word, and it's a pretty simple one at that. 

What would help users is to enter something much smaller, without pressing
multiple times, and let the SlimServer try to work out what it was the user was
trying to enter. 

Solution
In this solution the user must put in the same number of characters as the
words, word or word part that he is interested in, but only use the first
character on the appropriate key rather than pressing multiple times. So, "
ABBA" becomes "AAAA" and "PINK FLOYD" becomes " PGMJ DJMWD". 

Implementing this is fairly easy, and involves just modifying the two Perl
functions in "Slim/Music/Info.pm" that perform the comparisons during search
operations. These functions are "filter()" (for artists and albums), and
"filterHashByValue()" (for song titles). 

The modifications to the comparisons performed in these functions involve
translating the string being compared into the equivalent "lazy" format before
comparing it with the input from the user. For simplicity, the original text is
also checked in case the user has taken the trouble of multi-tapping in a full
search string. 

This translation can be performed easily in Perl, as follows:
$lazy =~ tr/ABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890 /
	    AAADDDGGGJJJMMMPPPPTTTWWWW.ADGJMPTW  /;

This translation set matches the text printed in the remote - you can see that
"WXYZ" all map to "W", for example, just like on the real remote.

Returning to the example, the user's entry of "AAAA" for " ABBA" will now match
against the lazy format translated from the plain-text version held in the
database because the text "ABBA" will have been translated to " AAAA" before
the comparison. It may also match other unwanted results due to the mapping of
characters from many-to-one (such as that well-known band "BAAB", amongst
others), but hopefully that's a small price to pay for speeding and simplifying
search entry. 

Using this method the previously poor example of "PINK FLOYD" is reduced from
22 key presses to just 10 - much better. 

Enhancing the Solution for Shared Keys
While the solution works very well for "PINK FLOYD", it's not quite optimal for
"ABBA" due to the characters sharing the same key. This means that to enter the
lazy form of "AAAA" the user has to enter a right-arrow after each character,
meaning that the four character lazy-form actually becomes seven characters.
Alternatively, the user has to wait between entering each character. Neither of
these cases are much if any quicker than multi-tapping out the full search
string in the first place - again, there must be a better way. 

Admittedly, "ABBA" is probably the worst case, but it shows that we still have
a little work to do. 

The enhancement works on the basis that if the user were to enter "ABBA"
without regard to the fact that the letters are on the same keys he would end
up with "2", and if he entered "STONES" he'd get "PTNDP" - note that the "ON"
ended up being a single "N" because they're on the same key. 

Now, if we translate the user's input with this in mind, we can get back to the
lazy-form needed for the basic solution and just search as before. 
We do this by going through the user's search entry and translating each
character into one or more characters that we put into the actual search
string, using an algorithm such as the following: 

$lazy = "";
for each $c in $entry {
    $d = "A" when $c eq "A";
    $d = "AA" when $c eq "B";
    $d = "AAA" when $c eq "C";
    $d = "AAAA" when $c eq "4";
    $d = "D" when $c eq "D";
    $d = "DD" when $c eq "E";
    $d = "DDD" when $c eq "F";
    ...
    $lazy = $lazy . $d;
} 

(Note that this is a simplification - the actual implementation uses a hash to
combine the lookup and translation.)

Fortunately (for a simple implementation), this translation can be done in the
same functions modified above ("filter()" and "filterHashByValue()"), thus
minimising the impact of the patch. 

Conclusion
This method definitely results in some false-positives being returned, but
given the gobbledygook that you tend to get when when entering such lazy forms
(such as in the examples given here, even in the "ABBA" example), they should
be few and the time to skip through these in the search results should be much
less than the time to carefully spell the search out correctly. Also, the more
characters entered the less likely false-positives are, and since it's now
quicker to enter the search in the first place it's therefore easier to enter
more useful search terms than before. 

In practice, false-positives do not seem to occur that often. On my 6000-ish
track database, searching for "MONEY" (encoded as "ODW"), correctly comes back
with 10 tracks containing my target word, and two tracks containing the word
"MOODY". Not bad for just three characters.

Another disadvantages is that the search will take longer due to checking
against both the 'raw' user search string and the lazy-encoded version. Again,
this should be eased with the more efficient database in SlimServer 6. In
practice, however, I can notice little or difference on my server. 

These drawbacks may mean that this method of searching isn't for everyone. 
An enhancement might be that rather than always also searching against the
lazy-forms, a server preference allows the user to choose to make the search
work harder or not. I've left this as an exercise for this SlimServer
developers, however!

Note: I've developed the patch against the 10th January 2005 nightly of version
5.4.1. However, given the 'insertion' nature of the changes that I've made I
should think it will apply to some later versions as well. Note that I would be
surprised if this applied against the 6.0 development branch given its database
changes, but I've not tried it so anything is possible. 

An additional caveat is that I'm not experienced in developing SlimServer
patches and so I may have overlooked some quite fundamental things in putting
this together. It certainly works reliably for me and I'm very pleased with it,
but I'm using an English character set and may not have checked that everything
else still works as before. Warnings aside, however, I'm reasonably confident
in it. 

You're free to apply this patch yourselves, but I can only offer limited help
with it. If you're not comfortable with modifying the SlimServer source
yourself my advice is to not do it and wait until (hopefully) it finds its way
into the real SlimServer software. 

If one of the SlimServer developers with access to CVS would like to
incorporate this patch (or one based on it) into SlimServer then I would be
very pleased. All I ask is a credit in the ChangeLog.

Installation Instructions

Linux
1. Download the above patch and put it somewhere on the machine to patch
(right-click the above link and choose "Save Link As...");
2. Change directory to the SlimServer directory (i.e. the one containing the
main "slimserver.pl" file);
3. Apply the patch with:
patch -p0 < [lazy-search-path]
(Replacing [lazy-search-path] with the pathname you downloaded the patch to).
4. All being well you should see the following:
patching file Slim/Music/Info.pm
And if there are no errors then the patch has applied smoothly.
5. Restart SlimServer and start enjoying lazy searches.

Microsoft Windows
I use SlimServer on Linux and so I've no experience of how this might be
applied on Windows. However, I can probably have a reasonable guess:
1. Make sure you're running the "Perl Version" of the SlimServer rather than
the ".EXE" version. This is because this is going to modify the source and not
rebuild the EXE for you.
2. Download the above patch and put it somewhere on the machine to patch
(right-click the above link and choose "Save Link As...");
3. Change directory to the SlimServer directory (i.e. the one containing the
main "slimserver.pl" file);
4. Apply the patch with:
patch -p0 < [lazy-search-path]
(Replacing [lazy-search-path] with the pathname you downloaded the patch to).
5. All being well you should see the following:
patching file Slim/Music/Info.pm
And if there are no errors then the patch has applied smoothly.
6. Restart SlimServer and start enjoying lazy searches.

The patch program is probably not going to be installed on your Windows
machine. I've not tested it, but I've used some Windows ports of Unix commands
from http://unxutils.sourceforge.net/ before and they've worked well, and I
know a version of patch is provided here.

Does anything similar exist for the 6.1/6.2 builds?  I understand these are full
re-writes vs. 5.4 so I assume the patch would not work.

Thanks for the interest. I'm working on something for the 6.2 builds in slower
time - I've not had a great deal of time to look at it but it's definitely on my
plans. I'll keep this bug updated and drop something on the mailing lists if and
when I make any progress. I'm certaininly planning on getting it working as I've
found it excellent and it takes away all of the main of searching using the
remote (for me, anyway).

Stuart,

Is your work on this something that could possibly be done as a plugin?  It
might be easier to "work in" on an ongoing basis if there is any way.  If you
need added hooks into the server, that might be possible as well.

Of course, no worry if Dean wants to include this in the core.  I'm mainly
thinking to save you total rework later if, once again, its left aside.

I'm far from familiar from plugins, but I didn't think they extended to the kind
of approach I'd taken with the patch. In 6.2, the process works by adding
columns to the database (which I've got working), populating those columns with
the "lazy" lazy-encoded versions of the current search text columns (which I've
got working), then also checking the lazy versions when searching (which I've
not got working yet).

I've had to do this by obviously editing the database creation script (I've left
the upgrade script alone for the moment), and then by editing the DataStores
Perl modules of the SlimServer source (eg Album.pm, but also Base.pm). As this
involves slipping lines into the existing code I wasn't aware that there were
sufficient plugin hooks available for that, and it still leaves the problem of
the database schema modification.

Still, you're clearly far more aware of what is and what is not possible with
plugins, so I'm prepared to be proved wrong!

I have now produced an updated version of this patch against SlimServer 6.2
(more specifically, revision 4101) - I've added it as a new attachment to this bug.

It's much cleaner than the 5.4.1 version I produced earlier in that it doesn't
get used for web searches (which may have been confusing), and because it's
still a single SQL query at the end of the day the search performance isn't
affected.

I've still not made this optional, but I'm planning on adding a preference for
that. I'd love for this to make its way into the mainline SlimServer source, but
I'll try to keep the patch up to date on my webpage anyway
(http://hickinbottom.demon.co.uk/SlimServer/lazy_searching.htm).

Created attachment 776 [details]
Patch against SlimServer 6.2 (revision 4101)

Created attachment 781 [details]
Patch against SlimServer 6.2 (revision 4117)

Updated patch that support SlimServer 6.2. Additionally, this patch adds a
per-player setting to enable/disable the lazy searching functionality - find it
on the "player settings->remote" screen of the web UI.

Created attachment 782 [details]
Patch against SlimServer 6.2 (revision 4117)

Sorry for the quick update - forgot to add a setting to the player's "Settings"
menu. That should just about be it now.

I wonder if there's a way that this could be turned into a plugin?  That way we can let folks create new 
input modes and not have to keep updating patches...

Yes, I'd prefer this as a plugin too.

I'll look at the hooks that are supported by the current plugin architecture and
see if I can suggest some new ones to support this kind of thing (I'm assuming
there aren't ones already there as I didn't see any hook calls in the code I was
looking through and modifying for this patch). The later versions of the patch
doesn't modify the database schema and so that probably simplifies
"pluginification" somewhat.

I don't think it will take much work; I'll post back to this bug when I've made
some progress.

Created attachment 847 [details]
Patch+plugin against SlimServer 6.2 (revision 4416)

I’ve gone away and worked some more on this, with the result attached. It
is now in two parts:

1. A patch against SlimServer (revision 4416 in this case)
2. A plugin

The patch to SlimServer adds two new hooks–one that lets interested
parties filter the ‘search’ text before it is stored in the
database during an import/scan, and another that lets interested parties filter
the search text before it is used to search the database.

Although the patch is against r4416, i expect it’ll apply to nearby
revisions in either direction.

The plugin utilises these hooks to store and search using the
‘lazy’ form I’ve described earlier. This newer version
includes help text viewable through the web interface, and gives the user the
ability to enable and disable lazy searching through the player itself (under
the “Plugins→Lazy Searching” menu).

Remember that you need to rescan the database after patching and installing the
plugin to allow the search to work.

Hopefully this form of submission will be more acceptable; it’s
well-commented and on its own the patch does nothing more than add hooks that
are unused in the stock SlimServer source–the behaviour of the server for
the user is unchanged. I’ve tried to make the SlimServer modifications
open to providing similar search plugins possible by not being too specific.

Feedback on the patch would be welcome; if the form of the hooks needs to be
modified before they could be added to the SlimServer trunk I’ll do that
and adapt the plugin to follow if at all possible. I’m be really keen to
get this in (the patch at least–the plugin I’m happy to keep
separately supplied if that helps).

Sorry about the messed-up punctuation above. Also, the attachment seems to have
lost its name; use “lazy-patch-4416.tar.gz” to ensure it opens OK.

what format is the attachment 847 [details]?
tried getting it as a zip, .gz and tar.gz.  all come out corrupt.

Created attachment 861 [details]
SlimServer patch for search hooks (r4416)

Hmmm - I'm not sure what happened there, sorry. Try this one (this is the
SlimServer patch on its own (plain text); I'll post the plugin as a separate
attachment).

Created attachment 862 [details]
LazySearch plugin (0.1) - tar.gz

Here's the Lazy Search plugin. It should be a .tar.gz file.

I've created a new version of the plugin. This dynamically performs searching as
you type and is modelled very much after the stock 'search' button, so it's much
clearer what's going on.

This still needs the hooks into the database encoding I provided in the previous
SlimServer patch, but no longer needs to hook into the existing 'search' button
as it's an entire replacement button. That probably makes the SlimServer patch a
little more acceptable as it's cleaner.

I've not attached a version of that plugin, but I've attached a small video that
shows it in action searching for "Dark Side of the Moon" by just pressing the
four keys for "DARK". I think it looks pretty good.

The video is DIVX, and should be saved as an AVI file.

Created attachment 900 [details]
Video of a dynamic version of the plugin

This a DivX video, and should be saved as "lazyvid.avi" or similar.

I've posted a plugin for SlimServer 6.2 and later, that does not require any
server patches, to here:
http://hickinbottom.demon.co.uk/slimserver/lazy-searching/lazy-searching2.htm

Dean doesn't work here any more :)

Unassigned bugs cannot have a priority.