Improve fuzzy search for in the Pod::Source class about core

[fabiopelosin]

@floere You might have some insight about this domain, so if you have some suggestion I would be really interested in hearing them.

[fabiopelosin]

Note: The PermissiveResearch appears to implement the fuzzy logic that we are after.

[fabiopelosin]

Moreover I think that the search logic should be extracted from the Pod::Source class.

[floere]

@irrationalfab Thanks for pointing this out to me. I'm happy to help and I do have some insight. I don't know yet what the use case is – from your entry it seems we are looking for fuzzy_match, but also taking into account the case? (Or is there more?) In other words: How can I help?

[fabiopelosin]

I will elaborare more on later, for now these are the tests of the current implementation.

I don't know yet what the use case is

I'm open to suggestions just looking for a way to help in case of misspells in the Podfile and to simplify commands like pod spec cat which currently does the following:

$  pod spec cat AFNet
[!] More than one spec found for 'AFNet':
AFNetworkActivityLogger, AFNetworking, AFNetworking-RACExtensions, AFNetworking-ReactiveCocoa, AFNetworking-Synchronous

[floere]

@irrationalfab I guess using a web API is out of the question, right?

[alloy]

@floere Yeah in principle the tool should be able to work offline.

[floere]

Would a two stage process 1. Online, 2.  Fallback offline be an idea?

On Tue, Dec 3, 2013 at 11:56 AM, Eloy Durán [email protected]
wrote:

@floere Yeah in principle the tool should be able to work offline.

Reply to this email directly or view it on GitHub:
#42 (comment)

[alloy]

Why would we do that? That sounds like we need more code complexity to be able to fall back to something we could already be doing in the first place?

[fabiopelosin]

I agree that a dual approach would add too much complexity. Also I don't see any reason to have it online. I think that we should implementing the correct algorithm and then it could be used by CocoaPods and by any web service interested in this feature.

[floere]

I agree with both of you that a dual approach is not necessary currently.

But for the sake of a technical discussion, let me describe why I asked:
I ran the new fuzzy search and noticed that with 2900 specs on my 2.3 GHz i7 the search takes about 0.5 s.
This of course is very reasonable.
However, this search currently indexes the specs each time the command is run – and that is an implementation that makes sense – and the time to index grows linearly with the number of specs available. I don't know the current spec amount growth rate, but I assume it's quite impressive. Assuming some improvements to the fuzzy search, the time to search might well go up to 1 s today, and easily to 2 s and so on with 6000 specs etc. (Also note that this search does not use multiple processors. On a similar note though: Moore's Law helps a little.)

But then again, it works and is reasonably fast – I suggest we revisit this when necessary. Also, as noted in the CP chat – we can always cache the index, too.

Next up: Ideas for improving this search, much more fun ;) I guess the question is whether we want to go for tpyo coreciton first or for multi word queries, or or…?

[fabiopelosin]

👍

Next up: Ideas for improving this search, much more fun ;) I guess the question is whether we want to go for typo coreciton first or for multi word queries, or or…?

I would focus on typo correction and then in support for abbreviations. I'm not sure if the same algorithm should be used. To clarify about type corrections I mean a quicksilver style match (keeping in mind that we live in a camel case world):

"mc" => "Mission Control"
"mv" => "MacVim"
"ap" => "App Store", "Application Loader"

[floere]

And I guess also

"misco" => "Mission Control"
"mavi" => "MacVim"

And, true, those would be two different algorithms - we can decide whether those would cascade (prefix first, then typo only if nothing is found) or are combined.

[fabiopelosin]

👍

[fabiopelosin]

Currently I'm of the opinion that we should support two algorithms:

• Misspell correction: the usage case is misspells in the Podfile and git like suggestions in CocoaPods subcommands in case the command is not found.
  • case correction
  • similar strings match (Levenshtein distance?)
• Abbreviation search: the usage case is improved interaction with commands taking the name of a Pod as argument ($ pod spec info ARAn).

Given that there is interest in supporting the search for similar strings in CLAide we should identify if we want to use an external dependency. However as this match would be pretty simple and would have limited performance requirements as the subcommands are limited the implementation in CLAide could be done without pulling any dependency.

[alloy]

@irrationalfab Can you given an example of what you mean by ‘in the Podfile’ ?

[fabiopelosin]

Podfile:

pod 'ARanalytics'

Command line:

$ pod install
[... I'm happily doing my and the sky is blue ...]
Unable to find a specification for `ARanalytics`... did you mean `ARAnalytics`?

Computer simulation of the user reaction:

[alloy]

Hahaha. Gotcha, makes complete sense! 💃

To be clear, you mean that it would still fail the install, right?

[fabiopelosin]

To be clear, you mean that it would still fail the install, right?

Absolutely!

[segiddins]

Closing as out of scope -- I think we have too many pods to really make this feasible anyways.