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
8 EUR/month (paid per year)
Advertisements:
Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously
J
 JaroWinkler
 Johnson's algorithm
 JohnsonTrotter
 JSort
 J sort
 jump list
 jump search
JaroWinkler
(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 FellegiSunter 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 Recordlinkage Methodology a Applied to Matching the 1985 Census of Tampa, Florida, Journal of the American Statistical Association, 89:414420.
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 BellmanFord 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.)
BellmanFord algorithm, Dijkstra's algorithm.
Note:
After [CLR90, page 569].
Author: PEB
JohnsonTrotter
(algorithm)
Definition:
Generate permutations by transposing one pair of elements at a time.
Also known as SteinhausJohnsonTrotter.
Generalization (I am a kind of ...)
permutation.
Author: PEB
More information
Hale F. Trotter, Perm (Algorithm 115), CACM, 5(8):434435, 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):282285, July 1963. Available at http://www.jstor.org/sici?sici...E or http://www.jstor.org/action/...846
JSort
(algorithm)
Definition:
An inplace sort that partially orders the array twice with buildheap, once moving lesser items earlier and once in reverse moving greater items later, then uses insertion sort on the nearlyordered array.
Generalization (I am a kind of ...)
inplace sort.
Aggregate child (... is a part of or used in me.)
buildheap, insertion sort, heap.
Note:
The implementation attributes the algorithm to Jason Morrison, Carleton University.
Author: PEB
J sort
(algorithm)
Definition:
An inplace 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 ...)
inplace sort.
Aggregate child (... is a part of or used in me.)
strand sort, shuffle sort.
Note:
Called "quicker 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  n ^{1/3}, to item i + i ^{1/3}. At the top level, items 1³, 2³, 3³, ..., n ^{1/3} ³ have backward links, that is, there is a link from item i³, 1 < i ≤ n ^{1/3} ³, to item (i1)³. Search, insert, and delete are O(n^{1/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):10911103, 1995.
jump search
(algorithm)
Definition:
Search a sorted array by checking every j^{th} 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=n^{2/3} for the first jumps and j=n^{1/3} for the second level of jumps.
Author: PEB
More information
Ben Shneiderman, Jump Searching: A Fast Sequential Search Technique, CACM, 21(10):831834, October 1978.
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
