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
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 - 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 (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.
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
|