| package com.android.nn.benchmark.util; |
| |
| /** Utilities for operations on sequences. */ |
| public final class SequenceUtils { |
| private SequenceUtils() {} |
| |
| /** |
| * Calculates Levenshtein distance between 2 sequences. |
| * |
| * This is the minimum number of single-element edits (insertions, deletions or substitutions) |
| * required to change one sequence to another. |
| * See: https://en.wikipedia.org/wiki/Levenshtein_distance |
| */ |
| public static int calculateEditDistance(int[] seqA, int[] seqB) { |
| int m = seqA.length; |
| int n = seqB.length; |
| int[][] d = new int[m + 1][n + 1]; |
| |
| for (int i = 0; i <= m; ++i) { |
| d[i][0] = i; |
| } |
| |
| for (int j = 1; j <= n; ++j) { |
| d[0][j] = j; |
| } |
| |
| for (int i = 1; i <= m; ++i) { |
| for (int j = 1; j <= n; ++j) { |
| int substitutionCost = (seqA[i - 1] == seqB[j - 1]) ? 0 : 1; |
| d[i][j] = Math.min( |
| Math.min(d[i - 1][j] + 1, d[i][j - 1] + 1), |
| d[i - 1][j - 1] + substitutionCost); |
| } |
| } |
| return d[m][n]; |
| } |
| |
| public static int indexOfLargest(float[] items) { |
| int ret = -1; |
| float largest = -Float.MAX_VALUE; |
| for (int i = 0; i < items.length; ++i) { |
| if (items[i] > largest) { |
| ret = i; |
| largest = items[i]; |
| } |
| } |
| return ret; |
| } |
| } |