Algorithms and Data Structures Glossary Free glossaries at TanslationDirectory.com translation jobs
Home Free Glossaries Free Dictionaries Post Your Translation Job! Free Articles Jobs for Translators

Algorithms and Data Structures Glossary
(Starting with "J")

By www.nist.gov,
Gaithersburg, Maryland, U.S.A.

paul . black [at] nist . gov
http://www.nist.gov/dads




Become a member of TranslationDirectory.com at just $12 per month (paid per year)




Advertisements:



Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously



A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

J

Jaro-Winkler
Johnson's algorithm
Johnson-Trotter
JSort
J sort
jump list
jump search

Jaro-Winkler

(algorithm)

Definition: A measure of similarity between two strings. The Jaro measure is the weighted sum of percentage of matched characters from each file and transposed characters. Winkler increased this measure for matching initial characters, then rescaled it by a piecewise function, whose intervals and weights depend on the type of string (first name, last name, street, etc.).

Generalization (I am a kind of ...)
string matching with errors.

Note: For "piecewise function", see the definition in MathWorld or answers from Dr. Math.

Author: PEB

More information

William E. Winkler and Yves Thibaudeau, An Application of the Fellegi-Sunter Model of Record Linkage to the 1990 U.S. Decennial Census, Statistical Research Report Series RR91/09, U.S. Bureau of the Census, Washington, D.C., 1991.
Matthew A. Jaro, UNIMATCH: A Record Linkage System: User's Manual, Technical Report, U.S. Bureau of the Census, Washington, D.C., 1976.
Matthew A. Jaro, Advances in Record-linkage Methodology a Applied to Matching the 1985 Census of Tampa, Florida, Journal of the American Statistical Association, 89:414-420.


Johnson's algorithm

(algorithm)

Definition: An algorithm to solve the all pairs shortest path problem in a sparse weighted, directed graph. First, it adds a new node with zero weight edges from it to all other nodes, and runs the Bellman-Ford algorithm to check for negative weight cycles and find h(v), the least weight of a path from the new node to node v. Next it reweights the edges using the nodes' h(v) values. Finally for each node, it runs Dijkstra's algorithm and stores the computed least weight to other nodes, reweighted using the nodes' h(v) values, as the final weight. The time complexity is O(V²log V + VE).

Aggregate child (... is a part of or used in me.)
Bellman-Ford algorithm, Dijkstra's algorithm.

Note: After [CLR90, page 569].

Author: PEB


Johnson-Trotter

(algorithm)

Definition: Generate permutations by transposing one pair of elements at a time.

Also known as Steinhaus-Johnson-Trotter.

Generalization (I am a kind of ...)
permutation.

Author: PEB

More information

Hale F. Trotter, Perm (Algorithm 115), CACM, 5(8):434-435, August 1962. Available at http://doi.acm.org/10.1145/368637.368660
Selmer M. Johnson, Generation of Permutations by Adjacent Transposition, Mathematics of Computation, 17(83):282-285, July 1963. Available at http://www.jstor.org/sici?sici...E or http://www.jstor.org/action/...846


JSort

(algorithm)

Definition: An in-place sort that partially orders the array twice with build-heap, once moving lesser items earlier and once in reverse moving greater items later, then uses insertion sort on the nearly-ordered array.

Generalization (I am a kind of ...)
in-place sort.

Aggregate child (... is a part of or used in me.)
build-heap, insertion sort, heap.

Note: The implementation attributes the algorithm to Jason Morrison, Carleton University.

Author: PEB


J sort

(algorithm)

Definition: An in-place sort algorithm that uses strand sort to sort fewer than about 40 items and shuffle sort to sort more.

Generalization (I am a kind of ...)
in-place sort.

Aggregate child (... is a part of or used in me.)
strand sort, shuffle sort.

Note: Called "quick-er sort" by one Théodore Myshrall in an apparent plagiarism for a 1998 school project.

Author: PEB

More information

John Cohen says in a message posted in 1997 that he invented this algorithm.


jump list

(data structure)

Definition: A variant of doubly linked list with items in sorted order and having two levels of additional links that span geometrically increasing distances. For a list with n items, the next level is a link from item i, 1 ≤ i ≤ n - floor( n 1/3), to item i + floor( i 1/3). At the top level, items 1³, 2³, 3³, ..., floor( n 1/3) ³ have backward links, that is, there is a link from item i³, 1 < i ≤ floor( n 1/3) ³, to item (i-1)³. Search, insert, and delete are O(n1/3) worst case.

Note: The data structure can also be seen as a binary search tree with additional links.

Author: PEB

More information

Arne Andersson and Thomas Ottmann, New Tight Bounds on Uniquely Represented Dictionaries, SIAM Journal of Computing, 24(5):1091-1103, 1995.


jump search

(algorithm)

Definition: Search a sorted array by checking every jth item until the right area is found, then doing a linear search. The optimum for n items is when j=√ n.

Also known as block search.

Generalization (I am a kind of ...)
search.

Note: If there will be two levels of jumping, the optimum is j=n2/3 for the first jumps and j=n1/3 for the second level of jumps.

Author: PEB

More information

Ben Shneiderman, Jump Searching: A Fast Sequential Search Technique, CACM, 21(10):831-834, October 1978.



A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

 

Published - April 2009








Find free glossaries at TranslationDirectory.com

Find free dictionaries at TranslationDirectory.com

Subscribe to free TranslationDirectory.com newsletter

Need more translation jobs from translation agencies? Click here!

Translation agencies are welcome to register here - Free!

Freelance translators are welcome to register here - Free!

Submit your glossary or dictionary for publishing at TranslationDirectory.com






Free Newsletter

Subscribe to our free newsletter to receive news from us:

 

Menu

Use More Glossaries
Use Free Dictionaries
Use Free Translators
Submit Your Glossary
Read Translation Articles
Register Translation Agency
Submit Your Resume
Obtain Translation Jobs
Subscribe to Free Newsletter
Buy Database of Translators
Obtain Blacklisted Agencies
Vote in Polls for Translators
Read News for Translators
Advertise Here
Read our FAQ
Read Testimonials
Use Site Map

Advertisements

translation directory

christianity portal
translation jobs


 

 
Copyright © 2003-2024 by TranslationDirectory.com
Legal Disclaimer
Site Map