---
# System prepended metadata

title: Generiek matchingalgoritme in Go

---

# Generiek matchingalgoritme in Go

:::info
**Type document**: Onderzoeksdocument, WBSO
**Auteur**: Luciano Nooijen, Bytecode
**Documentversie**: 0.1.0, 11 september 2020
:::

## Introductie

Voor zowel Dearly als voor Youngpwr is het idee om op termijn een algoritme te gaan ontwikkelen voor in eerste instantie filtering, en later ook voor recommendations. Naast Dearly en Youngpwr is dit ook een algoritme wat voor veel andere projecten in de toekomst ingezet kan worden.

Ik stel dit document op om enkele ideeen uiteen te zetten, die besproken en geevalueerd kunnen worden binnen Bytecode, en eventueel later geimplementeerd kunnen worden.

## Project-specifiek of generiek?

Een belangrijke keuze voor de bouw van het algoritme is of we per project een aangepaste versie willen hebben, of een generiek algoritme. Het voordeel van een versie per project is dat we het per project het algoritme gemakkelijk kunnen tweaken, echter weegt dit mijns inziens niet op tegen nadelen van duplicate code binnen projecten. 

Omdat dit algoritme niet zo specifiek is als bijvoorbeeld de JWT-generatie en wachtwoord hashing die in elke Go-codebase van ons voorkomt, lijkt het me het beste om het matching algoritme als een los project te ontwikkelen, of om het eerst te ontwikkelen binnen een project, en zodra de API stabiel is het als losse dependency aan te gaan roepen.

## Is Go de juiste keuze?

Eerder heb ik nog getwijfeld of Go de juiste taal was om dit algoritme in te ontwikkelen. Dit omdat Go geen ondersteuning biedt voor bijvoorbeeld generics.

Echter biedt voor het matchingalgoritme, en daarnaast ook zeker later voor recommendations/sorting de struct tags fuctionaliteit van Go een enorme meerwaarde. Om alles typesafe te houden zullen we wat omweggetjes moeten nemen, maar dit zou geen probleem moeten zijn. Het is wel goed in gedachten te houden dat er in de toekomst Generics-support zal komen voor Go.

## Gebruik van `interface{}` voor een basis filter algoritme

Omdat er in Go geen generics aanwezig zijn zal het nodig zijn om gebruik te maken van `interface{}` als input en output types.

De type definitie van de functie zou dan zijn:

```go
func Matcher(input []interface{}, requirements interface{}) (output interface{}, error)
```

Binnen de `Matcher`-functie wordt er gebruik gemaakt van de `reflect` package vanuit de Go standard library. Via reflection wordt de `input` naast de `requirements` gelegd en wordt er bepaald welke `input` items `output` mag bevatten. Ook kan de volgorde van `output` worden vastgesteld, hierover zo meer.

Deze oplossing zou alleen goed werken voor een algoritme zonder support voor bijvoorbeeld slices, of selectiecriteria op basis van 'one-of'.

### Type safety

Het is belangrijk om het gebruik van `interface{}` zo lokaal mogelijk te houden. Zo is het mogelijk om typesafe functies binnen een Go domain te maken:

```go
func MatchUsers(userDataSet: []User, filters UserFilters)([]User, error) {
    matchedUsersUntyped, err := matcher.Matcher(userDataSet, filters)
    if err != nil {
        return err
    }
    matchedUsersTyped, ok := matchedUsersUntyped.([]User)
	if !ok {
        return nil, errors.New("convertion to []User failed")
	}
    return matchedUsersTyped, nil
}
```

Met deze opzet is het mogelijk om typed `MatchUsers` aan te roepen, en een typed response te krijgen. Dit is dus een omweg voor generics.

## Gebruik van struct tags

Om meer controle te hebben binnen het algoritme kan er gebruikt worden van de struct tags van Go. Hier kan meer data in worden meegegeven voor het matchingalgoritme:

```go
type User struct {
    Name string
    Gender string
    Age int
    State string
    Expertises []string
}

type UserFilterCriteria struct {
    Gender *string `input:"Gender"` // Pointers naar string/int, om nil mogelijk te maken
    AgeMin *int `input:"Age" filtertype:"min"`
    Age *int `input:"Age" filtertype:"exact"`
    AgeMax *int `input:"Age" filtertype:"max"`
    StateInclude []string `input:"State" filtertype:"oneof"`
    StateExclude []string `input:"State" filtertype:"noneof"`
    Expertises []string `input:"Expertises" filtertype:"all"`
}
```

## Sorteren van uitkomsten

Bij een compleet algoritme zijn er de volgende stappen aanwezig:

1. **Dataset**: Genereren van een dataset die voor een gebruiker beschikbaar zijn. Dit gebeurt voordat het algoritme wordt aangeroepen. Denk hierbij op het uitfilteren van reeds bestaande matches bij een match-platform.
2. **Filtering**: De beschikbare dataset samen met eisen voor filtering meegegeven aan een algoritme, die alle data-entries die niet aan deze eisen voldoen wegfiltert. Voor een aanbevelingsalgoritme zou deze stap overgeslagen kunnen worden (dus een lege eisen)
3. **Sortering**: De dataset die overblijft na filtering wordt gesorteerd op bepaalde factoren, om ervoor te zorgen dat de resultaten van beste naar minste match worden teruggegeven (geen must-have voor eerste versie)

Voor filtering is het dan nodig om naast `requirements` ook `wishes` mee te geven. Dit kan bijvoorbeeld het profiel zijn van de aanvragende gebruiker, of persoonlijke voorkeuren van een persoon. Dit zou de volgende functiedefintie geven:

```go
func Matcher(input []interface{}, requirements interface{}, wishes interface{}) (output interface{}, error)
```

Hierbij zijn `requirements` en `wishes` van hetzelfde struct-type. Dit kan niet worden gecheckt met generics, maar wel met reflection, waarna een error kan worden teruggegeven als het gaat om verschillende struct types. 

Echter kan er nog over worden nagedacht om het type van `wishes` gelijk te maken aan dat van het slice-type van `input`. Op deze manier kan een lading aan gebruikers worden meegegeven, plus de gebruiker die de aanvraag doet om zo de best passende gebruikers mee te geven. Echter wordt hier dus geen rekening gehouden met bijvoorbeeld een man die juist een vrouw zoekt, dus er zou een pre-processing stap nodig zijn om de gebruiker om te vormen naar input voor `wishes`. Voor nu lijkt het mij het beste om `type requirements === type wishes` aan te houden.

Om het filteren mogelijk te maken is een optie om binnen de data van de struct uit te breiden met een score-systeem. Per entry wordt er dan nagegaan of er een overeenkomst is met de data binnen wishes, en zo ja een score opgeteld. Op basis van deze score wordt de slice met output gesorteerd en teruggegeven aan de caller.

Het aangeven van de scores is op de volgende manier te doen:

```go
type UserFilterCriteria struct {
    Gender *string `input:"Gender" matchvalue:"100"`
    AgeMin *int `input:"Age" matchvalue:"50"`
    Age *int `input:"Age" matchvalue:"150"`
    AgeMax *int `input:"Age" matchvalue:"50"`
    StateInclude []string `input:"State" filtertype:"oneof" matchvalue:"50"` // Value per match
    StateExclude []string `input:"State" filtertype:"noneof" matchvalue:"-100"`
    Expertises []string `input:"Expertises" filtertype:"all" matchvalue:"25"`
}
```

Met het sorteren zijn de mogelijkheden eindeloos. Er kunnen ook systemen ontwikkeld worden waarmee bijvoorbeeld een score gegeven wordt op basis van hoe dicht waardes bij elkaar zitten (leeftijd wens 30 en gegeven 28 een betere score geven dan wens 30 en gegeven 50).

## Technische knelpunten

Go is geen Rust als het gaat om memory safety en het is ook geen Elm waarbij geen runtime errors mogelijk zijn. Om het algoritme zo solide te krijgen dat er niet onnodig fouten - of erger, panics - ontstaan, is het belangrijk om:

* Te onderzoeken of het mogelijk is om in case-statements te forceren dat alle mogelijke reflect types afgewerkt moeten worden en er anders linting fouten ontstaan (voor zover ik weet is dit niet mogelijk binnen Go)
* Vooraf een goed model van foutafhandeling in te bouwen, waarmee bruikbare en actionable errors kunnen worden teruggegeven aan de gebruiker, mogelijk met stacktraces van acties die ondernomen zijn
* Er moet goed worden nagedacht over de testbaarheid van het algoritme en een goede testopzet, zodat we het algoritme kunnen testen niet alleen met zowel kleine testsets (worden uit twee kleine structs de juiste eruit gefilters), als grote datasets (grote set input die op de juiste volgorde terugkomt)
* Het is belangrijk dat er gemeten wordt hoe goed de resultaten zijn die uit de sortering stap komen, of de profielen die uit een suggestiealgortime komen. Dit om te het algoritme (specifiek de `matchvalue` waarden) goed af te kunnen stellen. 
    * Goede tracking en beoordeling hoe goed matches zijn is dus belangrijk. De uitdaging hierin is: de juiste data opslaan op de juiste manier, zodat we deze conclusies kunnen trekken.
    * Later is het wellicht mogelijk om met deze data neural networks te trainen of om gebruik te maken van AI om de correcte waarden te berekenen, al is dit wel in een veel later stadum.

## ~~Open-source~~ ***vrije software***

Tot nu toe ben heb ik nog niet veel tijd besteed aan het zoeken naar soortgelijke projecten, maar van wat ik heb gezocht is dit er nog niet. Zeker omdat dit voor veel bedrijven "hun digitale goud" is.

Echter lijkt me dit voor ons een heel goed project om beschikbaar te maken voor anderen, waar we mogelijk ook nog best fans op internet kunnen genereren.

Als het project publiek op Github staat heeft het ons ook wel weer een klein voordeeltje, dat we geen gekke truucjes uit hoeven te halen met `go get` voor authorizatie met private repos.

## Financieel

Zodra we een solide algoritme hebben staan dat werkt met onbekende data en betrouwbare output geeft (ongeacht het input type) verwacht ik dat commercieel ook erg interessant is. Voor het gebruik van het algoritme en het inbouwen kunnen we een vaste fee vragen. Wellicht kunnen we bij Youngpwr en Dearly de betalingsbereidheid testen.

Dat de tool open-source is lijkt me ook geen groot probleem, omdat klanten het zelf waarschijnlijk niet in kunnen bouwen en de fee niet alleen is voor het gebruik, maar ook voor het inbouwen ervan.

Als we tracking voor uitkomsten hebben (dus optimalisatie kunnen uitvoeren voor klanten binnen de fee die ze betalen) en wellicht zelfs kunnen aanbieden om een tornado aan buzzwords (ai, neural networks, fuck it, we slaan de big data op in een blockchain of we gaan met internet of things de berekeningen met quantum computing doen \s) erop los te laten, kan dat voor bepaalde mensen ook een groot pluspunt zijn. Voor ons ook wel weer een gave les om met AI/NN aan de slag te gaan.

## Ontwikkeling

Het lijkt me goed om - ongeacht de status van Dearly en/of Youngpwr - het onderzoek naar mogelijk implementaties en `reflection` in Go op te starten binnenkort, met als eerste doel om binnen enkele dagen een simpele proof of concept te hebben voor puur de filtering, zonder tests en niet helemaal fool-proof.

Met het proof of concept kunnen we een goed beeld vormen van wat de technische uitdagingen en valkuilen zullen zijn, en hoe we hier het beste mee om kunneng gaan. Ook hebben we dan een beter beeld bij hoeveel uur het kost om te ontwikkelen (en om bij projecten te integreren). Met deze kennis kunnen we de keuze maken het zelf direct te ontwikkelen, of om het te doen tegen een vergoeding van een klant (of meerdere klanten, een soort crowdcourcing).
