﻿ Algorithms and Data Structures Glossary (Starting with "J")
 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

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

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

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

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

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

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

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