TECHNIQUES FOR TOKENIZING URLS

• US 20090083266A1
• Filed: 11/06/2007
• Published: 03/26/2009
• Est. Priority Date: 09/20/2007
• Status: Abandoned Application

• Current Assignee: Oath Inc. (Verizon Communications Inc.)
• Original Assignee: Oath Inc. (Verizon Communications Inc.)
• Inventors: Poola, Krishna Leela, Ramanujapuram, Arun
• Application Number:
  US11/935,622
• Publication Number:
  US 20090083266A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 16/9566 URL specific, e.g. using aliases, detecting broken or misspelled links

Abstract

Techniques are described for tokenizing a corpus of URLs of web documents. URLs are first tokenized based upon specified generic delimiters to form components. The components are then tokenized using website-specific delimiters. Website-specific delimiters are any non-alphanumerical symbol or a unit change that is specific to a particular website. Support for website-specific delimiters and the tokens resulting from website-specific delimiters are calculated. Support values for website-specific delimiters and the tokens above a specified threshold value are valid. Tokenization may also be performed by generating a graph of the corpus of URLs of web documents. Each node of the graph represents a token and each edge represents a delimiter of the URLs. The graph is traversed and the support of the edges are compared to a specified threshold value. If the support of an edge of a node is greater, then the token corresponding to the node is valid.

Claims

1. A method for tokenizing URLs, comprising:

tokenizing, based upon generic delimiters, URLs of each of a plurality of documents of a website into a plurality of components;

for each particular component of the plurality of components, locating website-specific delimiters in the particular component;

calculating a delimiter support threshold for each particular website-specific delimiter of located site-specific delimiters;

determining whether delimiter support for each particular website-specific delimiter is greater than a specified delimiter support threshold;

in response to determining that the site specific delimiter support for the particular website-specific delimiter is greater than the specified delimiter support threshold, tokenizing the particular component based upon the particular website-specific delimiter;

for each particular token of the particular component, calculating a token support threshold for the particular token;

determining whether token support for the particular token is greater than a specified token support threshold; and

in response to determining that the token support for the component token is greater than the specified token support threshold, using the particular token to generate a description of the website.

2. The method of claim 1, wherein generic delimiters comprise the characters “

/,”

“

\”

“

&

,” and

“

=”

.

3. The method of claim 1, wherein locating website-specific delimiters further comprises identifying, in the particular component, a change of one particular type of character to another type of character, not of the particular type.

4. The method of claim 3, wherein types of characters comprise (1) a number type or (2) a letter type.

5. The method of claim 1, wherein website-specific delimiters comprise the characters corresponding to ASCII codes 32-37, 39-46, 58-60, 62-64, 91-96,and 123-127.

6. The method of claim 1, wherein delimiter support is calculated by determining a percentage of URLs of the plurality of documents of the website that have the same delimiter in the same location of the URL.

7. The method of claim 1, wherein token support is calculated by:

subtracting a number of distinct tokens in a same location of a URL by a number of URLs of the plurality of documents of a website to calculate a difference;

dividing the difference by the number of URLs of the plurality of documents to calculate a quotient;

multiplying the quotient by 100 to calculate the token support.

8. The method of claim 1, wherein token support and delimiter support are based upon measures from Information Theory.

9. A method of tokenizing URLs, comprising:

tokenizing, based upon generic delimiters and website-specific delimiters, URLs of each of a plurality of documents of a website into a plurality of components;

generating a graph wherein (a) each node of the graph represents components and (b) edges connecting the nodes represent delimiters;

associating a weight to each node and each edge;

for each particular node of the graph, traversing from the particular node to another node connected by an edge;

comparing the weight of the edge to a specified delimiter support threshold;

if the weight of the edge is greater than the specified delimiter support threshold, then including the node in a set of validated nodes;

if the weight of the edge is not greater than the specified delimiter support threshold, then traversing the graph until reaching a node where the number of incoming edges is equal to the number of nodes in a previous level; and

generating a description of the website based at least in part on the validated nodes.

10. The method of claim 9, wherein the weight of a node is a number of occurrences the component of the node occurs in the URLs of the plurality of documents in a same location of the URL.

11. The method of claim 9, wherein the weight of an edge is a number of occurrences the components, corresponding to the nodes connected by the edge, occurs together with the delimiter, corresponding to the edge, in the URLs of the plurality of documents.

12. The method of claim 9, wherein the weight of an edge and the weight of a node are based upon measures from Information Theory.

13. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to:

tokenize, based upon generic delimiters, URLs of each of a plurality of documents of a website into a plurality of components;

for each particular component of the plurality of components, locate website-specific delimiters in the particular component;

calculate a delimiter support threshold for each particular website-specific delimiter of located site-specific delimiters;

determine whether delimiter support for each particular website-specific delimiter is greater than a specified delimiter support threshold;

in response to determining that the site specific delimiter support for the particular website-specific delimiter is greater than the specified delimiter support threshold, tokenize the particular component based upon the particular website-specific delimiter;

for each particular token of the particular component, calculate a token support threshold for the particular token;

determine whether token support for the particular token is greater than a specified token support threshold; and

in response to determining that the token support for the component token is greater than the specified token support threshold, use the particular token to generate a description of the website.

14. The computer-readable storage medium of claim 13, wherein generic delimiters comprise the characters “

/”

“

!,”

“

&

,” and

“

=”

.

15. The computer-readable storage medium of claim 13, wherein locating website-specific delimiters further comprises identifying, in the particular component, a change of one particular type of character to another type of character, not of the particular type.

16. The computer-readable storage medium of claim 15, wherein types of characters comprise (13) a number type or (14) a letter type.

17. The computer-readable storage medium of claim 13, wherein website-specific delimiters comprise the characters corresponding to ASCII codes 32-37, 39-46, 58-60, 62-64, 91-96, and 123-127.

18. The computer-readable storage medium of claim 13, wherein delimiter support is calculated by determining a percentage of URLs of the plurality of documents of the website that have the same delimiter in the same location of the URL.

19. The computer-readable storage medium of claim 13, wherein token support is calculated by:

subtracting a number of distinct tokens in a same location of a URL by a number of URLs of the plurality of documents of a website to calculate a difference;

dividing the difference by the number of URLs of the plurality of documents to calculate a quotient;

multiplying the quotient by 100 to calculate the token support.

20. The computer-readable storage medium of claim 13, wherein token support and delimiter support are based upon measures from Information Theory.

21. A computer-readable storage medium carrying one or more sequences of instructions which, when executed by one or more processors, causes the one or more processors to:

tokenize, based upon generic delimiters and website-specific delimiters, URLs of each of a plurality of documents of a website into a plurality of components;

generate a graph wherein (a) each node of the graph represents components and (b) edges connecting the nodes represent delimiters;

associate a weight to each node and each edge;

for each particular node of the graph, traverse from the particular node to another node connected by an edge;

compare the weight of the edge to a specified delimiter support threshold;

if the weight of the edge is greater than the specified delimiter support threshold, then include the node in a set of validated nodes;

if the weight of the edge is not greater than the specified delimiter support threshold, then traverse the graph until reaching a node where the number of incoming edges is equal to the number of nodes in a previous level; and

generate a description of the website based at least in part on the validated nodes.

22. The computer-readable storage medium of claim 21, wherein the weight of a node is a number of occurrences the component of the node occurs in the URLs of the plurality of documents in a same location of the URL.

23. The computer-readable storage medium of claim 21, wherein the weight of an edge is a number of occurrences the components, corresponding to the nodes connected by the edge, occurs together with the delimiter, corresponding to the edge, in the URLs of the plurality of documents.

24. The computer-readable storage medium of claim 21, wherein the weight of an edge and the weight of a node are based upon measures from Information Theory.