Slice Distance : An Insert-Only Levenshtein Distance with a Focus on Security Applications

• Levenshtein distance is well known for its use in comparing two strings for similarity. However, the set of considered edit operations used when comparing can be reduced in a number of situations. In such cases, the application of the generic Levenshtein distance can result in degraded detection and computational performance. Other metrics in the literature enable limiting the considered edit operations to a smaller subset. However, the possibility where a difference can only result from deleted bytes is not yet explored. To this end, we propose an insert-only variation of the Levenshtein distance to enable comparison of two strings for the case in which differences occur only because of missing bytes. The proposed distance metric is named slice distance and is formally presented and its computational complexity is discussed. We also provide a discussion of the potential security applications of the slice distance.

Subject headings

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Keyword

Measurement

Pattern matching

Time complexity

Transforms

Security

DNA

Computer Science

Datavetenskap

Publication and Content Type

ref (subject category)

kon (subject category)