Jans Blog

Blog

Umzug zu Github Pages

23.12.2016

Heute habe ich meinen Blog von Wordpress zu Jekyll umgezogen, damit ich leichter Beiträge verfassen kann. Der größte Vorteil durch die Umstellung ist die Möglichtkeit, offline zu schreiben und später via git push die Veröffentlichung anzustoßen. Gehostet wird über Github Pages. Das verwendete Theme nennt sich hagura.

Internet defekt – Techniker ist informiert

23.05.2016

Nach einem Umzug mit Unitymedia dauerte es länger als einen Monat, bis wieder Internet zur Verfügung stand. Grund war eine Störung, über deren Existenz Unitymedia widersprüchliche Angaben machte. Die volle Geschichte:

MensaUPB 2.18.7

Metal Only 0.4.16

06.12.2015

Nachdem rbrtslmn keine Zeit mehr hatte, die Entwicklung fortzuführen, habe ich die offzielle Android-App von Metal Only e.V. übernommen. Die neueste Änderung ist der Fix eines Absturzes, der über Google Play gemeldet wurde.

metal-only-release-0.4.16

MensaUPB 2.18.6

22.11.2015

Seit 2.15.4 gab es einige Bug-Fixes und ein paar Funktionserweiterungen. Hier eine kurze Aufführung:

  • Bugs behoben:
    • Ladebildschirm wurde nicht richtig gezeigt.
    • Wenn man von einem Gericht zurück ging, kam man zur falschen Gerichte-Liste
    • Design-Problem behoben: das Bild eines Gerichts verdeckt nicht mehr den ganzen Bildschirm wenn man das Handy quer hält (Detailansicht)
    • Bildhintergrund in Menü-Ansicht wurde auf Tablets plötzlich größer
    • Fehler behoben: Gerichte, die vom STW aufgetauscht wurden, werden nun auch in der App korrekt aktualisiert
  • App merkt sich nun das letzte Restaurant
  • Erste Schritte gemacht, um Öffnungszeiten anzuzeigen. Zudem wird nun angezeigt, wenn eine Einrichtung geschlossen ist (betrifft nur Termine, die auf studentenwerk-pb.de veröffentlicht wurden)
  • Anonyme Nutzungsstatistiken, um Anwendung zu optimieren

Download: MensaUPB-2.18.6

MensaUPB 2.15.4

23.04.2015

Primär Verbesserungen im Design: MensaUPPB-2.15.4

MensaUPB 2.15.0

29.03.2015

Verbesserungen in der Oberfläche und folgende Fehler wurden behoben:

  • Auswahl-Kreise in Navigation entfernt

  • Von einem Gericht kommt man zur richtigen Kombo von “Tag & Restaurant” zurück

MensaUPB-2.15.0

Mockup Node Detailscreen

06.03.2015

Some mockups for a node detail screen… Looking for a designer nonetheless 😉

Mock: online freifunk node

 

Mockup: Offline freifunk node

MensaUPB 2.11.2

10.02.2015

Kleine Fixes ggü. 2.11.1 (Feature regression)

MensaUpb-2.11.2

MensaUPB 2.11.1

08.02.2015

Neu:

  • Infos werden nun auch auf englisch gezeigt
  • Es wird nun eine Notiz statt einem Ladebildschirm gezeigt, wenn es an einem Tag kein Essen gibt
  • Fehler behoben: Wechsel des Restaurants wechselt unter bestimmten Umständen den Tag

Download: MensaUPB-2.11.1

MensaUPB 2.9.0

18.01.2015

Neu: Campus Mensae in einer Liste!

MensaUPB-2.9.0

Verworfen aufgrund von größerem Bug: Pull to refresh; Download: MensaUPB-2.8.5

Cleaning some data with Clojure 3

30.12.2014

The first post in this series was about the original problem: there is a data-set of strings with potential duplicates and many typos. The second was about computing the similarity of two strings. In this post we will focus on the question

Can we group multiple strings of a set by similarity?

Matching the names: The first step is to match the names. I hope, that the following code is documented good enough.

(defn- singleMap 
  "Produces a function that takes one argument str2 and computes
  [str1 str2 (f str1 str2)]."
  [f str1]
  (fn [str2]
    [str1 str2 (f str1 str2)]))

(defn- split? 
  "Produces a split predicate based on a."
  [str] 
  (fn [x] 
    (pos? (compare str x))))

(defn- getAfterStr 
  "Returns the elements after str of the supplied sequence"
  [str strings]
  (get (split-with (split? str) strings) 1))

(defn- singleMapWAll
  "Produces a producer function that maps the matching function
  with a to all elements after a."
  [f strings] 
  (fn 
    [str1] 
    (map (singleMap f str1) getAfterStr)))

(defn match
  "Uses the given similarity function f and matches all
  strings with each other string once"
  [f strings]
  ; Applys the function produced by singleMapWAll to strings
  ; and concatenates the result
  (mapcat (singleMapWAll f strings) strings)) 

The following table provides some more information. a, b, c, d, and e are the strings to be matched. “f str1” denotes that a function “f str1” is mapped onto the corresponding string in the last row (which will be used as str2 in the matching).

(f d)
(f c f c)
(f b f b f b)
(f a f a f a f a)
a b c d e

Whereas map would produce a mapping as above, mapcat applys the mapping and concatenates the results as displayed below.

(f a f a f a f a f b f b f b f c f c f d)
a b c d e c d e d e e

After all matching fs are applied, we get our result tuples in one list:

([a b (f a b)] [a c (f a c)] [d e (f d e)])

Filtering the results: This filtering step is just an intermediate step. We will use the results find good “grouping” values. Remember that a result vector has the form [str1 str2 (similarity str1 str2).

(defn- minSimFilterBuilder 
  [min-sim]
  (fn [x]
    (>= (get x 2) min-sim)))

(defn- unequalName? 
  [x]
  (not (= (get x 0) (get x 1))))

(defn cleanMatches 
  [matches min-sim]
   (filter (minSimFilterBuilder min-sim) 
    (filter unequalName? matches)))

minSimFilterBuilder is used to construct filter functions based on a minimum similarity value. The function unequalName? simply checks, if the names of the result tuple are different. The result of cleanMatches will then contain only matches with distinct strings that are “similar enough” for us.

Constructing clusters: sadg

Cleaning some data with Clojure 2

27.12.2014

Cleaning some data with Clojure 1” provides some context on this project. This post here focusses on the question

“Can we tell, if two strings are similar?”.

Levenshtein Distance: My first idea was to use the Levenshtein Distance. This metric counts the minimum number of operations needed to transform one string into the other when allowing insertion, deletion or substition of characters. Its definition is as follows:

Definition of Levenshtein Distance<figcaption class="wp-caption-text">Definition of Levenshtein Distance</figcaption></figure>

indicator_functiondenotes the indicator function, which is equal to 0 when the i-th character of a is equal to the j-th character of b. Otherwise it’s 1.

Transforming this into clojure-code is fairly simple, given the definitions. First, the indicator-function:

(defn indicator
  "0, if the i-th character of a and the j-th character of b
are the same. 1 otherwise."
  [a b i j]
  (if (= (get a (dec i)) (get b (dec j)))
   0
   1))

Next, a helper function which will be called recursively:

(defn lev
  "Helper function to compute the levenshtein distance"
  [a b i j]
  (if (zero? (min i j))
   (max i j)
   (min (inc (lev a b (dec i) j))
        (inc (lev a b i (dec j)))
        (+ (lev a b (dec i) (dec j)) (indicator a b i j)))))

And finally the “public api”:

(defn levenshtein
  "Computes the Levenshtein distance between two strings a and b"
  [a b]
  (lev a b (count a) (count b)))

Unfortunately, this solution is not very performant [0]. Also it blows the stack somewhere above 50 characters (tested for 140 characters). Nonetheless, this is enough for my use-case 😉

=> (def alphabet "alphabetdefghijklmnopqrstuvwxyz")
#'/alphabet
=> (time (levenshtein (subs alphabet 0 10) (subs alphabet 0 10)))
"Elapsed time: 3855.856306 msecs"
0
=> (time (levenshtein (subs alphabet 0 11) (subs alphabet 0 11)))
"Elapsed time: 21493.424412 msecs"
0

We have this performance issue because most values are computed multiple times; some are computed extremely often. The solution in this case is a well-placed memoize to reuse the computed values: (def lev (memoize lev)). All in all we get a huge performance boost [1]:

=> (time (levenshtein (subs alphabet 0 11) (subs alphabet 0 11)))
"Elapsed time: 1.230304 msecs"
0
=> (time (levenshtein (subs alphabet 0 15) (subs alphabet 0 15)))
"Elapsed time: 1.280788 msecs"
0
=> (time (levenshtein alphabet alphabet))
"Elapsed time: 3.099704 msecs"
0
=> (time (levenshtein rnd_50_1 rnd_50_2))
"Elapsed time: 11.464978 msecs"
38
=> (time (levenshtein rnd_140_1 rnd_140_2))
StackOverflowError clojure.lang.AFn.applyToHelper (AFn.java:148)

Note, that “rnd_X_Y” are distinct pseudo-random strings that were “generated” by hitting the keyboard X times.

Extending this metric: This metric does not take into account that \”o is equivalent to ö. We can fix this by replacing these special values with more common ones before computing the distances:

(defn cleanString
  "A hacky cleaning function. Replaces unusual characters by more common ones."
  [s]
  (switch "\"A" "Ä"
   (switch "\"O" "Ö"
    (switch "\"U" "Ü"
     (switch "\"a" "ä"
      (switch "\"o" "ö"
       (switch "\"u" "ü"
        (switch "\\ss{}" "ß" s))))))))))))

And for a vector etc. of strings:

(defn clean 
  "Cleans a vector of strings"
  [strings]
  (map cleanString strings))

From distance to similarity: Our next step is to convert distances between two strings into a “similarity value”. The Levenshtein distance of two strings is (<= 0 (levenshtein a b) (max (count a) (count b))). Therefore we can convert a Levenshtein distance to a similarity metric as follows:

(defn levensthein-similarity
  "Computes a similarity measure based on Levenshtein distance. 0 ~ a and b completely different, 1 ~ a and b equal"
  [a b]
  (- 1 (/ (levensthein a b)
          (max (count a) (count b)))))

TL;DR: Use an appropriate String Metric and convert it to a similarity metric. I tried out Levenshtein Distance which does not takes into account that \”o and ö are equivalent.

[0] “We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.” (Knuth, Donald. Structured Programming with go to Statements, ACM Journal Computing Surveys, Vol 6, No. 4, Dec. 1974. p.268.); from clean-code-developer.de

[1] These numbers mean next to nothing: we don’t know yet if these improvements hold true for random strings. This will probably be on a later post.


Edit: Better code listings.

 

 

Cleaning some data with Clojure 1

25.12.2014 Just playing around with some distance measures for strings and some test data.

Krombels Dash 0.1.1

14.12.2014

Kleinere fixes, und Anpassungen an das Krombel Design.

Deinstallation vor update notwendig: krombel-0.1.1

ffpb-krombel

Krombels Dashboard auf Android

14.12.2014

Ein kleiner Prototyp, der Krombels Dashboard auf Android Geräte bringt: krombel-0.1.0.

Features:

  • Automatische Updates
  • Benachrichtigung bei neuen Highscores

Die App ist nicht über den Play Store verfügbar; dies wird später der Fall sein. Quellcode gibt es auf github.

ffpb-krombel-device

MensaUPB 2.7.5

12.12.2014

MensaUPB-v2.7.5

Neu:

  • Schnellere Synchronisation
  • Erster Einblick ins “Material Design”
  • Übersichtlicherer Speiseplan durch optische Trennung der Menüs
  • Bilder werden in der Detailansicht geladen und angezeigt
  • Erste Teile wieder in English
  • “Badges” (vegan, laktosefrei, …) werden angezeigt
  • Neue Kategorien im GrillCafe

MensaUPB 2.7.0

29.11.2014

MensaUPB-2.7.0 als Beta veröffentlicht. Neu sind hier vor allem die Badges (laktosefrei, glutenfrei, vegan, …).

Hier noch die Unterschiede zur Play Store Version:

  • Schnellere Synchronisation
  • Einblick ins “Material Design”
  • Übersichtlicherer Speiseplan durch optische Trennung der Menüs
  • Bilder werden in der Detailansicht geladen und angezeigt
  • Erste Teile wieder in English

MensaUpb 2.4.0

17.11.2014

MensaUpb-2.4.0 … mit einem ersten Blick auf das Material Design. Bisher nur die support library version angepasst.

MensaUPB 2.3.0

14.11.2014

MensaUPB-2.3.0

  • Schnellere Synchronisation bei erstem Start
  • Interne Verbesserungen

MensaUPB 2.1.9

08.11.2014

MensaUPB-2.1.9

Behoben: Manche Gerichte wurden in der Übersichtsliste fehlerhaft mit “Preis/100g” ausgezeichnet.

MensaUPB 2.1.7

01.11.2014

Kleinere Fixes: MensaUPB-2.1.7

MensaUPB 2.1.5

16.10.2014

Bei einigen Benutzern kam es zu einem Absturz nach dem Upgrade. Dieser wurde nun behoben: MensaUPB-2.1.5

MensaUPB 2.1.3

14.10.2014

Ein neues Release. Seit einiger Zeit im PlayStore, jetzt auch hier: MensaUPB 2.1.3

  • Wechsel auf neue API des Studentenwerks
  • Einige Fehler behoben

MensaUPB Beta

26.09.2014

Ab heute gibt es ein Beta-Release von MensaUPB mit der neuen API des Studentenwerks. Um diese zu testen, müsst ihr folgendes tun:

  1. Tretet der Google+ Community oder der Beta-Mailingliste bei.
  2. Anschließend besucht ihr diese Seite und werdet Tester.
  3. Sollte die App noch nicht installiert sein, könnt ihr diese aus dem Play Store herunterladen.

Falls die App bereits installiert ist, entfällt der letzte Schritt: es gibt ein automatisches Update auf die Beta-Version.

Ihr könnt jederzeit unter dieser Seite entscheiden, ob ihr Tester sein wollt oder nicht. Die App “wechselt” dann automatisch.

OpenVPN der UPB unter Linux

31.05.2014

Auf den Seiten des IMT findet sich eine Anleitung zum Einrichten des VPN-Zugriffs. Dort wird auch eine .conf-Datei bereitgestellt, welche vom Benutzer importiert werden soll. Da diese bei mir einige Probleme verursachte (VPN Zugriff nicht möglich, Freeze im Einstellungsbildschirm), habe ich folgende Ergänzungen zur IMT-Anleitung:

  • Beide Pfade (upb-network-ca.pem und Network_Certificate.p12) müssen in der Datei enthalten sein und absolut angegeben werden
  • “resolv-retry infinite” wurde entfernt (der oben genannte Freeze wurde durch eine Endlosschleife verursacht)

Hier eine von mir minimal korrigierte openvpn-upb. Die Pfade (s.o.) müssen noch korrigiert werden.

Edit: broken Link durch Redesign der Uni-Homepage gefixt.

MensaUPB 1.8.0

24.05.2014

Auf expliziten Wunsch wurden in dieser Version die Preise hinzugefügt. Diese sind noch etwas buggy (Preise pro 100g werden ohne “pro 100g” dargestellt), jedoch sind die wichtigsten Gerichte aka Vorschlagsmenüs korrekt angezeigt.

MensaUPB-1.8.0

MensaUPB 1.6.0

25.04.2014

Neue Funktionen:

  • Automatischer Wechsel zur Abendmensa zwischen 14:00 und 19:30
  • Abendmensa hat Freitags nicht geöffnet – statt Ladebildschirm wird nun eine Notiz gezeigt

Apk: MensaUPB-1.6.0

Fachschaftsdroid 0.0.9

18.04.2014

Ein kleiner Bugfix, der einen reproduzierbaren Absturz behebt: fsdroid-v0.0.9

MensaUPB veröffentlicht

17.04.2014 Vor einigen Tagen war es endlich so weit: die Open Source App MensaUPB konnte wieder im Play Store veröffentlicht werden.

Fachschaftsdroide Beta im Play Store

13.02.2014

Da die Versionsverwaltung über den Play Store deutlich einfacher als über diesen Blog ist, gibt es den Fachschaftsdroiden nun im Play Store als Beta. Testen könnt ihr wie folgt, die Reihenfolge der Schritte ist zu beachten:

  1. Fachschaftsdroide: zum Beta testen https://plus.google.com/communities/112299389493406857610 oder https://groups.google.com/d/forum/fachschaftsdroide-beta beitreten
  2. Danach als Tester im Play Store anmelden https://play.google.com/apps/testing/de.upb.fsmi
  3. Probleme, Wünsche per Email an ljan@mail.upb.de

Fachschaftsdroide 0.0.2

20.11.2013

Vor der Installation müssen unbekannte Quellen aktiviert werden, eine Anleitung gibts auf https://github.com/ironjan/MensaUPB.

Download: fsdroid-0.0.2

Fehlermeldungen/Feature-Wünsche bitte per Mail an mich.

Features:

  • Zeigt Öffnungststatus und Termin der nächsten Sitzung
  • Zeigt die Neuigkeiten von https://fsmi.uni-paderborn.de/
  • Zeigt die Kontaktdaten der Fachschaft mit Kontaktmöglichkeit

Bekannte Bugs/Ziele für die Beta:

  • Es gibt keine aussagekräftigen Fehlermeldungen
  • Die Kontakt-Seite sieht nicht so aus, als würde man von dort direkt kontaktieren können; wird überarbeitet
  • Die App ist relativ groß im Verhältnis zu den bisher implementierten Funktionen
  • Die Status-Karte und die “Sitzungskarte” im Bereich sind noch nicht optimal und werden überarbeitet.

Der Fachschaftsdroide

14.11.2013

Da der Fachschaftsdroide sich nun im Alpha-Stadium befindet, musste eine Seite zum Download her – das wäre dann mein “Blog under construction.

Vor der Installation müssen unbekannte Quellen aktiviert werden, eine Anleitung gibts auf https://github.com/ironjan/MensaUPB [0]

Download: fsdroid-alpha-0.0

Features:

  • Zeigt Öffnungststatus und Termin der nächsten Sitzung
  • Zeigt die Neuigkeiten von https://fsmi.uni-paderborn.de/
  • Zeigt die Kontaktdaten der Fachschaft mit Kontaktmöglichkeit

Bekannte Bugs:

  • Links in Neuigkeiten sind nicht klickbar
  • Es gibt keine aussagekräftigen Fehlermeldungen
  • Die Kontakt-Seite sieht nicht so aus, als würde man von dort direkt kontaktieren können

[0] Schamlose Eigenwerbung – der Downloadlink von MensaUPB is nicht mehr aktuell. Neues von MensaUPB gibts dann auch hier.