1

我在 Haskell 做一个任务。任务是在给定单词匹配、未命中和间隙插入分数的情况下给出两个字符串的最佳对齐方式。到目前为止，这是我们的代码。第一步是使用蛮力使其工作，稍后我们将使用记忆化来实现。但是，我们被困在当前位置。

我们的 optAlignment 函数无法正常工作。对于示例输入“writers”“vintner”，返回的最佳对齐应该是：

[("writ-ers","vintner-"), ("wri-t-ers","-vintner-"), ("wri-t-ers","v-intner-")]

但我们得到

[("writers","vintner"),("writ-ers","vintner-"),("writ-ers","v-intner"),("wri-ters","v-intner"),("wri-t-ers","v-intner-"),("writ-ers","-vintner"),("wri-ters","-vintner"),("wri-t-ers","-vintner-")]

所以正确的替代方案是存在的，但也有更多。我们制作了一个函数 totalScore，它表明我们得到的一些备选方案不是最优的（显然）。但是我们现在已经花了 2 个小时试图弄清楚，但没有取得任何进展。该代码还需要几分钟才能运行，这使得错误检查有点困难。

所以我们真的需要一些帮助来找出我们代码中的哪些部分是错误的。

-- String Alignment assignment

scoreMatch = 0
scoreMismatch = -1
scoreSpace = -1

type AlignmentType = (String,String)

optAlignments :: String -> String -> [AlignmentType]
optAlignments [][] = [("","")]
optAlignments (x:xs) [] = attachHeads x '-' (optAlignments xs "")
optAlignments [] (y:ys) = attachHeads '-' y (optAlignments "" ys)
optAlignments (x:xs) (y:ys) = maximaBy (uncurry similarityScore) $match++xSpacematch++ySpacematch
    where match = attachHeads x y $optAlignments xs ys
          xSpacematch = attachHeads x '-' $optAlignments xs (y:ys)
          ySpacematch = attachHeads '-' y $optAlignments (x:xs) ys



similarityScore :: String -> String -> Int
similarityScore [][] = 0
similarityScore xs [] = scoreSpace * length xs
similarityScore [] ys = scoreSpace * length ys
similarityScore (x:xs) (y:ys) = max match $max xSpacematch ySpacematch
    where match = similarityScore xs ys + score x y
          xSpacematch = similarityScore xs (y:ys) + score x '-'
          ySpacematch = similarityScore (x:xs) ys + score '-' y



score :: Char -> Char -> Int  
score x '-' = scoreSpace
score '-' y = scoreSpace
score x y
    | x == y = scoreMatch
    | otherwise = scoreMismatch

-- attachHeads functions attaches the two arguments to the front of each list in the tuple
attachHeads :: a -> a -> [([a],[a])] -> [([a],[a])] 
attachHeads h1 h2 aList = [(h1:xs,h2:ys) | (xs,ys) <- aList]

maximaBy :: Ord b => (a -> b) -> [a] -> [a] 
maximaBy valueFcn xs = [a| a <- xs, valueFcn a == maxVal ] 
    where maxVal = maximum $map valueFcn xs

totalScore x y = sum $map (uncurry score) (zip x y)
--map (uncurry totalScore)

--outputOptAlignments string1 string2
4

0 回答 0