1# Copyright 2015 The TensorFlow Authors. All Rights Reserved. 2# 3# Licensed under the Apache License, Version 2.0 (the "License"); 4# you may not use this file except in compliance with the License. 5# You may obtain a copy of the License at 6# 7# http://www.apache.org/licenses/LICENSE-2.0 8# 9# Unless required by applicable law or agreed to in writing, software 10# distributed under the License is distributed on an "AS IS" BASIS, 11# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12# See the License for the specific language governing permissions and 13# limitations under the License. 14# ============================================================================== 15"""Tests for tensorflow.kernels.edit_distance_op.""" 16 17import numpy as np 18 19from tensorflow.python.framework import constant_op 20from tensorflow.python.framework import ops 21from tensorflow.python.framework import sparse_tensor 22from tensorflow.python.ops import array_ops 23from tensorflow.python.platform import test 24 25 26def ConstantOf(x): 27 x = np.asarray(x) 28 # Convert to int64 if it's not a string or unicode 29 if x.dtype.char not in "SU": 30 x = np.asarray(x, dtype=np.int64) 31 return constant_op.constant(x) 32 33 34class EditDistanceTest(test.TestCase): 35 36 def _testEditDistanceST(self, 37 hypothesis_st, 38 truth_st, 39 normalize, 40 expected_output, 41 expected_shape, 42 expected_err_re=None): 43 edit_distance = array_ops.edit_distance( 44 hypothesis=hypothesis_st, truth=truth_st, normalize=normalize) 45 46 if expected_err_re is None: 47 self.assertEqual(edit_distance.get_shape(), expected_shape) 48 output = self.evaluate(edit_distance) 49 self.assertAllClose(output, expected_output) 50 else: 51 with self.assertRaisesOpError(expected_err_re): 52 self.evaluate(edit_distance) 53 54 def _testEditDistance(self, 55 hypothesis, 56 truth, 57 normalize, 58 expected_output, 59 expected_err_re=None): 60 # Shape inference figures out the shape from the shape variables 61 # Explicit tuple() needed since zip returns an iterator in Python 3. 62 expected_shape = [ 63 max(h, t) for h, t in tuple(zip(hypothesis[2], truth[2]))[:-1] 64 ] 65 66 # SparseTensorValue inputs. 67 with ops.Graph().as_default() as g, self.session(g): 68 # hypothesis and truth are (index, value, shape) tuples 69 self._testEditDistanceST( 70 hypothesis_st=sparse_tensor.SparseTensorValue( 71 *[ConstantOf(x) for x in hypothesis]), 72 truth_st=sparse_tensor.SparseTensorValue( 73 *[ConstantOf(x) for x in truth]), 74 normalize=normalize, 75 expected_output=expected_output, 76 expected_shape=expected_shape, 77 expected_err_re=expected_err_re) 78 79 # SparseTensor inputs. 80 with ops.Graph().as_default() as g, self.session(g): 81 # hypothesis and truth are (index, value, shape) tuples 82 self._testEditDistanceST( 83 hypothesis_st=sparse_tensor.SparseTensor( 84 *[ConstantOf(x) for x in hypothesis]), 85 truth_st=sparse_tensor.SparseTensor(*[ConstantOf(x) for x in truth]), 86 normalize=normalize, 87 expected_output=expected_output, 88 expected_shape=expected_shape, 89 expected_err_re=expected_err_re) 90 91 def testEditDistanceNormalized(self): 92 hypothesis_indices = [[0, 0], [0, 1], [1, 0], [1, 1]] 93 hypothesis_values = [0, 1, 1, -1] 94 hypothesis_shape = [2, 2] 95 truth_indices = [[0, 0], [1, 0], [1, 1]] 96 truth_values = [0, 1, 1] 97 truth_shape = [2, 2] 98 expected_output = [1.0, 0.5] 99 100 self._testEditDistance( 101 hypothesis=(hypothesis_indices, hypothesis_values, hypothesis_shape), 102 truth=(truth_indices, truth_values, truth_shape), 103 normalize=True, 104 expected_output=expected_output) 105 106 def testEditDistanceUnnormalized(self): 107 hypothesis_indices = [[0, 0], [1, 0], [1, 1]] 108 hypothesis_values = [10, 10, 11] 109 hypothesis_shape = [2, 2] 110 truth_indices = [[0, 0], [0, 1], [1, 0], [1, 1]] 111 truth_values = [1, 2, 1, -1] 112 truth_shape = [2, 3] 113 expected_output = [2.0, 2.0] 114 115 self._testEditDistance( 116 hypothesis=(hypothesis_indices, hypothesis_values, hypothesis_shape), 117 truth=(truth_indices, truth_values, truth_shape), 118 normalize=False, 119 expected_output=expected_output) 120 121 def testEditDistanceProperDistance(self): 122 # In this case, the values are individual characters stored in the 123 # SparseTensor (type DT_STRING) 124 hypothesis_indices = ([[0, i] for i, _ in enumerate("algorithm")] + 125 [[1, i] for i, _ in enumerate("altruistic")]) 126 hypothesis_values = [x for x in "algorithm"] + [x for x in "altruistic"] 127 hypothesis_shape = [2, 11] 128 truth_indices = ([[0, i] for i, _ in enumerate("altruistic")] + 129 [[1, i] for i, _ in enumerate("algorithm")]) 130 truth_values = [x for x in "altruistic"] + [x for x in "algorithm"] 131 truth_shape = [2, 11] 132 expected_unnormalized = [6.0, 6.0] 133 expected_normalized = [6.0 / len("altruistic"), 6.0 / len("algorithm")] 134 135 self._testEditDistance( 136 hypothesis=(hypothesis_indices, hypothesis_values, hypothesis_shape), 137 truth=(truth_indices, truth_values, truth_shape), 138 normalize=False, 139 expected_output=expected_unnormalized) 140 141 self._testEditDistance( 142 hypothesis=(hypothesis_indices, hypothesis_values, hypothesis_shape), 143 truth=(truth_indices, truth_values, truth_shape), 144 normalize=True, 145 expected_output=expected_normalized) 146 147 def testEditDistance3D(self): 148 hypothesis_indices = [[0, 0, 0], [1, 0, 0]] 149 hypothesis_values = [0, 1] 150 hypothesis_shape = [2, 1, 1] 151 truth_indices = [[0, 1, 0], [1, 0, 0], [1, 1, 0]] 152 truth_values = [0, 1, 1] 153 truth_shape = [2, 2, 1] 154 expected_output = [ 155 [np.inf, 1.0], # (0,0): no truth, (0,1): no hypothesis 156 [0.0, 1.0] 157 ] # (1,0): match, (1,1): no hypothesis 158 159 self._testEditDistance( 160 hypothesis=(hypothesis_indices, hypothesis_values, hypothesis_shape), 161 truth=(truth_indices, truth_values, truth_shape), 162 normalize=True, 163 expected_output=expected_output) 164 165 def testEditDistanceZeroLengthHypothesis(self): 166 hypothesis_indices = np.empty((0, 2), dtype=np.int64) 167 hypothesis_values = [] 168 hypothesis_shape = [1, 0] 169 truth_indices = [[0, 0]] 170 truth_values = [0] 171 truth_shape = [1, 1] 172 expected_output = [1.0] 173 174 self._testEditDistance( 175 hypothesis=(hypothesis_indices, hypothesis_values, hypothesis_shape), 176 truth=(truth_indices, truth_values, truth_shape), 177 normalize=True, 178 expected_output=expected_output) 179 180 def testEditDistanceZeroLengthTruth(self): 181 hypothesis_indices = [[0, 0]] 182 hypothesis_values = [0] 183 hypothesis_shape = [1, 1] 184 truth_indices = np.empty((0, 2), dtype=np.int64) 185 truth_values = [] 186 truth_shape = [1, 0] 187 expected_output = [np.inf] # Normalized, loss is 1/0 = inf 188 189 self._testEditDistance( 190 hypothesis=(hypothesis_indices, hypothesis_values, hypothesis_shape), 191 truth=(truth_indices, truth_values, truth_shape), 192 normalize=True, 193 expected_output=expected_output) 194 195 def testEditDistanceZeroLengthHypothesisAndTruth(self): 196 hypothesis_indices = np.empty((0, 2), dtype=np.int64) 197 hypothesis_values = [] 198 hypothesis_shape = [1, 0] 199 truth_indices = np.empty((0, 2), dtype=np.int64) 200 truth_values = [] 201 truth_shape = [1, 0] 202 expected_output = [0] # Normalized is 0 because of exact match 203 204 self._testEditDistance( 205 hypothesis=(hypothesis_indices, hypothesis_values, hypothesis_shape), 206 truth=(truth_indices, truth_values, truth_shape), 207 normalize=True, 208 expected_output=expected_output) 209 210 def testEditDistanceBadIndices(self): 211 hypothesis_indices = np.full((3, 3), -1250999896764, dtype=np.int64) 212 hypothesis_values = np.zeros(3, dtype=np.int64) 213 hypothesis_shape = np.zeros(3, dtype=np.int64) 214 truth_indices = np.full((3, 3), -1250999896764, dtype=np.int64) 215 truth_values = np.full([3], 2, dtype=np.int64) 216 truth_shape = np.full([3], 2, dtype=np.int64) 217 expected_output = [] # dummy; ignored 218 219 self._testEditDistance( 220 hypothesis=(hypothesis_indices, hypothesis_values, hypothesis_shape), 221 truth=(truth_indices, truth_values, truth_shape), 222 normalize=False, 223 expected_output=expected_output, 224 expected_err_re=(r"inner product -\d+ which would require writing " 225 "to outside of the buffer for the output tensor|" 226 r"Dimension -\d+ must be >= 0")) 227 228 229if __name__ == "__main__": 230 test.main() 231