1 package com.android.nn.benchmark.util; 2 3 /** Utilities for operations on sequences. */ 4 public final class SequenceUtils { SequenceUtils()5 private SequenceUtils() {} 6 7 /** 8 * Calculates Levenshtein distance between 2 sequences. 9 * 10 * This is the minimum number of single-element edits (insertions, deletions or substitutions) 11 * required to change one sequence to another. 12 * See: https://en.wikipedia.org/wiki/Levenshtein_distance 13 */ calculateEditDistance(int[] seqA, int[] seqB)14 public static int calculateEditDistance(int[] seqA, int[] seqB) { 15 int m = seqA.length; 16 int n = seqB.length; 17 int[][] d = new int[m + 1][n + 1]; 18 19 for (int i = 0; i <= m; ++i) { 20 d[i][0] = i; 21 } 22 23 for (int j = 1; j <= n; ++j) { 24 d[0][j] = j; 25 } 26 27 for (int i = 1; i <= m; ++i) { 28 for (int j = 1; j <= n; ++j) { 29 int substitutionCost = (seqA[i - 1] == seqB[j - 1]) ? 0 : 1; 30 d[i][j] = Math.min( 31 Math.min(d[i - 1][j] + 1, d[i][j - 1] + 1), 32 d[i - 1][j - 1] + substitutionCost); 33 } 34 } 35 return d[m][n]; 36 } 37 indexOfLargest(float[] items)38 public static int indexOfLargest(float[] items) { 39 int ret = -1; 40 float largest = -Float.MAX_VALUE; 41 for (int i = 0; i < items.length; ++i) { 42 if (items[i] > largest) { 43 ret = i; 44 largest = items[i]; 45 } 46 } 47 return ret; 48 } 49 } 50