Method to resolve an incorrectly entered uniform resource locator (URL)

• US 7,376,752 B1
• Filed: 10/28/2003
• Issued: 05/20/2008
• Est. Priority Date: 10/28/2003
• Status: Active Grant

• Current Assignee: David Chudnovsky, Gregory Chudnovsky
• Original Assignee: David Chudnovsky, Gregory Chudnovsky
• Inventors: Chudnovsky, Gregory V., Chudnovsky, David V.
• Primary Examiner(s): Cardone; Jason
• Assistant Examiner(s): Swearingen; Jeffrey R
• Application Number:
  US10/696,240
• Time in Patent Office: 1,666 Days
• Field of Search: 709/245
• US Class Current: 709/245
• CPC Class Codes: G06F 16/9566 URL specific, e.g. using aliases, detecting broken or misspelled links

Abstract

A method and a carrier medium carrying code segments to cause a processor to implement a method for resolving a possibly incorrectly entered URL. The method includes accepting the entered URL, parsing the accepted URL into URL parts, and carrying out a conventional URL lookup. In one embodiment, for any part of the accepted URL that is not valid, the method includes determining a signature for the accepted URL part; and conducting a fuzzy search for at least one valid URL part that is close to the invalid URL part according to a distance measure that combines at least one local measure, each measure suited for a particular type of URL part. At least one valid URL may be formed from the URL parts found in the fuzzy search. In one implementation, the conducting of the fuzzy search includes: determining at least one cluster of a set of pre-formed clusters wherein the accepted URL part is likely to be. Each cluster includes a set of valid URL parts that are close according to a distance measure, and has a representative URL part having a known signature. The determining of the cluster(s) includes finding the at least one signature of representative URLs close to the signature of the accepted URL part. The method includes further searching for a valid URL part within the at least one determined cluster.

Claims

1. A method comprising:

accepting a string of characters representing a possibly incorrectly entered URL;

parsing the string into a set of URL parts, a part formed from characters having values in a first space of characters, each part having a corresponding distance measure of closeness for measuring distances between URL parts;

forming a signature of each URL part, forming said signature including, in the case the distance measure of closeness for a URL part in the first space in integer valued, transforming the characters of the URL part whose values are in the first space into characters in a second space such that the distance measure of closeness is transformed to a distance measure of closeness that is not necessarily integer valued;

for each URL part, searching for at least one cluster of a set of pre-formed clusters, the set of pre-formed clusters being clusters of valid URL parts that are close according to the distance measure of closeness that is not necessarily integer valued, each cluster in the set of pre-formed clusters having a representative URL part and signature thereof, the searching using the signature of the URL part;

further searching for a valid URL part within each cluster found in the searching step,

wherein at least one URL part includes one or more non-text non-numerical characters.

2. A method for resolving a possibly incorrectly entered URL comprising:

accepting the entered URL;

parsing the accepted URL into URL parts;

carrying out a conventional URL lookup; and

for any part of the accepted URL that is not valid;

determining a signature for the accepted URL part; and

conducting a fuzzy search for at least one valid URL part that is close to the invalid URL part according to a distance measure that combines at least one local measure, each measure suited for a particular type of URL part,

wherein in the case the not-valid accepted URL part includes characters in a first space wherein a distance measure of closeness is integer-valued, the determining of the signature of the accepted URL part includes converting the first space into a second space such that the signature of the URL part is represented by one or more elements in the second space the second space being a space wherein the distance measure for comparing signatures of URL parts is non-integer or a general distance function in a metric space such that cluster analysis can be performed on signatures of valid URLs or URL parts, and

wherein at least one URL part includes one or more non-text non-numerical characters.

3. The method as recited in claim 2, further comprising forming at least one valid URLs from the URL parts found in the fuzzy search.

4. The method as recited in claim 3 further including the steps of:

displaying a list of formed URLs to a user of a IP client; and

prompting the user of the IP client to select a one of formed URLs in the list.

5. The method as recited in claim 2, wherein each URL part includes characters from a corresponding alphabet, the alphabet being of letters in the case of text, of phonemes in the case of sounds, of glyphs in the case of glyphs/images, and of numbers in the case of a numerical URL parts.

6. The method as recited in claim 2, wherein conducting the fuzzy search occurs at different parts of a computer network according to the type of part that was carrying out the conventional URL lookup determines is not valid.

7. The method as recited in claim 6, wherein the computer network is the Internet.

8. The method as recited in claim 6, wherein the computer network is a private network.

9. The method as recited in claim 2, wherein conducting the fuzzy search includes:

determining at least one cluster of a set of pre-formed clusters wherein the accepted URL part is likely to be, each cluster comprising a set of valid URL parts that are close according to a distance measure and having a representative URL part having a known signature, the determining including finding at least one signature of representative URLs close to the signature of the accepted URL part; and

further searching for a valid URL part within the at least one determined clusters.

10. The method as recited in claim 2, wherein the second space is n-dimensional Euclidean space such that the signature of the URL part is a sequence of n-dimensional vectors.

11. The method as recited in claim 10, wherein the values of the converted characters are on the unit sphere such that the second space is transformed to the n-dimensional unit sphere, wherein the signature of the URL part is a sequence of n-dimensional vectors on the unit sphere, and wherein calculating the distance between two URL parts can be carried out by a convolution-like operation on the signatures of the two URL parts.

12. The method as recited in claim 2, the local measures include at least one distance measures from the set consisting of a phonetic difference for URL parts for which sound comparison is appropriate, and image comparison for URL parts that include glyphs/images for which image comparison is appropriate, and a numerical difference for URL parts that are numerical and for which numerical comparison is appropriate.

13. The method as recited in claim 2, wherein the fuzzy search is performed at a client of a computer network.

14. The method as recited in claim 2, wherein the fuzzy search is performed at a server of a computer network.

15. A computer-readable medium having encoded thereon at least one computer readable code segment for instructing a processor of a processing system, the at least one code segment when executed carrying out a method for resolving a possibly incorrectly entered URL, the method comprising:

accepting the entered URL;

parsing the accepted URL into URL parts;

carrying out a conventional URL lookup; and

for any part of the accepted URL that is not valid;

determining a signature for the accepted URL part; and

conducting a fuzzy search at least one valid URL part that is close to the invalid URL part according to a distance measure that combines at least one local measure, each measure suited for a particular type of URL part,

wherein in the case the not-valid accepted URL part includes characters in a first space wherein a distance measure of closeness is integer-valued, the determining of the signature of the accepted URL part includes converting the first space into a second space such that the signature of the URL part is a sequence of values in the second space, the second space being a space wherein the distance measure for comparing signatures of URL parts is non-integer or a general distance function in a metric space such that cluster analysis can be performed on signatures of valid URLs or URL parts, and wherein at least one URL part includes one or more non-text non-numerical characters.

16. The computer-readable medium as recited in claim 15, wherein the method further comprises forming at least one valid URL from the URL parts found in the fuzzy search.

17. The computer-readable medium as recited in claim 15, wherein conducting the fuzzy search includes:

determining at least one cluster of a set of pre-formed clusters wherein the accepted URL part is likely to be, each cluster comprising a set of valid URL parts that are close according to a distance measure and having a representative URL part having a known signature, the determining including finding at least one signature of at least one representative URL close to the signature of the accepted URL part; and

further searching for a valid URL part within the at least one determined cluster.

18. The computer-readable medium as recited in claim 15, wherein the second space is n-dimensional Euclidean space such that the signature of the URL part is a sequence of n-dimensional vectors.

19. The computer-readable medium as recited in claim 18, wherein the values of the converted characters are on the unit sphere such that the second space is transformed to the n-dimensional unit sphere, wherein the signature of the URL part is a sequence of n-dimensional vectors on the unit sphere, and wherein calculating the distance between two URL parts can be carried out by a convolution-like operation on the signatures of the two URL parts.

20. The computer-readable medium as recited in claim 15, wherein the local measures include at least one distance measure from the set consisting of a string comparison measure for URL parts for which string comparison is appropriate, a phonetic difference for URL parts for which sound comparison is appropriate, and a numerical difference for URL parts that are numerical and for which numerical comparison is appropriate.

21. The computer-readable medium as recited in claim 15, wherein the local measures include one or more distance measures from the set consisting of a string comparison measure for URL parts for which string comparison is appropriate, a phonetic distance for URL parts for which sound comparison is appropriate, a glyph distance between images/icons for parts where it is appropriate, and a numerical distance for URL parts that are numerical and for which numerical comparison is appropriate.

22. A method of conducting a fuzzy search for a source URL part that closely matches a valid URL part, comprising:

determining a signature for the source URL part;

determining at least one cluster of a set of pre-formed clusters wherein the source URL part is likely to be, each cluster comprising a set of valid URL parts that are close according to a distance measure and having a representative URL part having a known signature, the determining of the likely clusters including finding at least one signature of representative URLs close to the signature of the accepted URL part; and

further searching for a valid URL part within the at least one determined cluster

wherein the source URL part includes at least one a non-text non-numerical symbol.

23. The method as recited in claim 22, wherein in the case the source URL part includes characters in a first space wherein a distance measure of closeness is integer-valued, the determining of the signature of the source URL part includes converting the first space into a second space such that the signature of the URL part is a sequence of values in the second space, the second space being a space wherein the distance measure for comparing signatures of URL parts is non-integer such that cluster analysis can be performed on signatures of valid URLs or URL parts.

24. The method as recited in claim 23, wherein the second space is n-dimensional Euclidean space such that the signature of the URL part is a sequence of n-dimensional vectors.

25. The method as recited in claim 24, wherein the values of the converted characters are on the unit sphere such that the second space is transformed to the n-dimensional unit sphere, wherein the signature of the URL part is a sequence of n-dimensional vectors on the unit sphere, and wherein calculating the distance between two URL parts can be carried out by a convolution-like operation on the signatures of the two URL parts.

26. A method comprising:

accepting a string of symbols representing a possibly incorrectly entered URL, at least one symbol being a non-text non-numerical symbol;

parsing the string into a set of URL parts, a part formed from characters having values in a first space of characters, each part having a corresponding distance measure of closeness for measuring distances between URL parts;

forming a signature of each URL part, forming said signature including in the case that the corresponding distance measure of closeness for the first space for at least one part is integer valued, transforming the characters of the URL part whose values are in the first space into characters in a second space such that the distance measure of closeness is transformed to a distance measure of closeness that is not necessarily integer valued;

for each URL part, searching for one or more clusters of a set of pre-formed clusters, the set of pre-formed clusters being clusters of valid URL parts that are close according to the distance measure of closeness that is not necessarily integer valued, but a general distance function in a metric space, each cluster in the set of pre-formed clusters having a representative URL part and signature thereof, the searching using the signature of the URL part;

further searching for a valid URL part within each cluster found in the searching step.